algorithm - 删除k个顶点后的连通分量数

Question

我正在尝试解决以下图形问题:

We are given a general unweighted and undirected graph and k (k < |V| ) vertices that are already known beforehand. The vertices are deleted sequentially. After each deletion, how many connected components are there?

我想到了在每一步都使用tarjan的算法来检查当前要删除的顶点是否是切割顶点，这样在执行删除时，我们可以简单地将邻居数添加到连通分量数。该算法的复杂度为O(V(V+E))。

有人告诉我有一个 O(V+E) 算法可以执行此任务。但我想不通。对谷歌的研究也没有透露太多。谁能告诉我吗？

Answer 1

我们可以利用顶点事先已知的事实。

让我们解决一个“反向”问题:给定一个图和一个按顺序添加到图中的顶点列表，计算每个添加结构后图中连通分量的数量。

解决方案非常简单:我们可以维护一个不相交的集合并集结构，并将与顶点关联的所有边添加到图中(很容易保持此结构中的组件数量:最初，它等于顶点，并在联合实际发生时减少一个)。

原始问题通过以下方式简化为“反向”问题:

1. 让我们将不与任何已删除顶点关联的所有边添加到不相交集并集。

2. 现在我们可以反转已删除顶点的列表，并按照上述方法将它们一一添加。

3. 之后，我们需要反转包含组件数量的结果列表。

注意:这个解实际上不是O(V + E)，它的O(V + E * alpha(V))，其中alpha( x) 是反阿克曼函数。对于所有实际用途，它都非常接近线性。