连接组件数

Question

我试图解决以下图表问题：

我们一般给出一个加权和无向图和K（K < | V |）是 已经顶点事先已知。顶点被顺序删除。每次删除 后，有多少个连接组件？

我想用的Tarjan的算法在每一步检查，如果当前顶点被删除是割点，从而进行了删除的时候，我们可以简单的邻居的号码添加到连接组件的数量。该算法的复杂度为O（V（V + E））。

有人告诉我，有一个O（V + E）算法来执行此任务。但我无法弄清楚。谷歌的研究也没有透露太多。任何人都可以请教我吗？

Answer 1

我们可以使用事先知道顶点的事实。我们来解决一个“反向”问题：给定一个图表和一个列表顶点，它们被顺序地加到它上面，在每个加法结构之后计算图中连接的组件的数量。

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

原来的问题归结为“反向”一个以下列方式：

1. 让我们补充说，没有入射到任何要删除的顶点到分离集工会的所有边缘。

2. 现在我们可以反转已删除顶点的列表，并按上面所述逐个添加它们。

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

注：该解决方案是不实际O(V + E)，其O(V + E * alpha(V))，其中alpha(x)是逆阿克曼的功能。对于所有实际目的而言，它非常接近线性。