时间戳

首页 > 解决方案 > 在跟踪组件数量时移除森林顶点

tree - 在跟踪组件数量时移除森林顶点

问题描述

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

我试过用这个公式

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

v被删除/恢复的顶点在哪里。

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

我考虑过颠倒查询顺序和/或使用不相交的集合，但这仍然会单独处理每个边缘。

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

标签： treegraph-theoryconnected-components

解决方案

好的，这就是我想出的：

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

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

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

推荐阅读