跟踪组件数量时删除森林顶点

Question

给定一棵具有 n 个顶点和 q 个查询 (n, q <= 5*10^5) 的树，其中对于每个查询，您可以删除或恢复先前删除的顶点，输出之后的连接组件数每次操作。

我试过使用这个公式

components = components + (removing ? 1 : -1)*(degree[v] - 1)

其中 v 是顶点 removed/recovered。

这里的问题是我必须跟踪所有度数，或者更新 v 所有邻居的度数，或者标记哪些节点被删除并通过检查它的哪个节点来计算 v 的度数邻居被删除，两种解决方案都需要迭代 v.

的邻接列表

我考虑过使用不相交的集合来颠倒查询顺序 and/or，但这仍然需要单独处理每条边。

有没有办法改进这个解决方案？

Answer 1

好的，这是我想出的：

首先，任意根树，同时计算父级和度数数组。我还使树有向，所以除了根之外所有的度数都小了一个，但这可能不是必需的。

现在更新节点时只需要更新父节点的度数。

sign = removing ? 1 : -1
if v == root
  components += sign*(deg[v] - 1)
else
  deg[parent[v]] -= sign
  components += sign*(deg[v] - deleted[parent[v]])

其中 deleted 是一个布尔数组。

还发现这适用于森林

components(E, V) = V - E

跟踪组件数量时删除森林顶点

Forest vertex removal while tracking number of components

tree

graph-theory

connected-components