algorithm - 拆解图算法

Question

一个图有n个顶点和m条边。该图开始连接，然后按照它们在列表中出现的顺序删除边。在该过程结束时，图形断开连接。

因此，在边列表中有一条特定的边，使得在删除它之前，有一个连通分量超过了 n/4 个顶点。去掉这条边后，图中没有超过n/4个顶点层的连通分量。

我将如何着手设计最佳算法来找到这条边。我是否只是开始删除边缘然后每次遍历图形以检查最大的连接组件是否足够？这在 O(nm) 时间内运行，但我觉得必须有一些更快的方法。我认为答案与使用不相交的集合来查找连接的组件有关，但我不确定如何着手实现它。

Answer 1

考虑反向运行此过程，添加边而不是删除边。这个过程与 Kruskal 的算法非常相似(每个节点都是自己开始的，边被添加到连接不同的连接组件中)，除了你一旦有至少一个连接组件具有至少 ⌊n/4⌋ 就停止其中的节点。

解决此问题的一种方法是使用 Kruskal 算法的修改版本和增强的联合查找数据结构，以便联合查找结构中的每个代表存储其连接组件中的节点数。以相反的顺序遍历边缘，如果端点已经连接，则在每个点丢弃边缘，否则将它们连接起来。如果您添加的边导致存在至少 ⌊n/4⌋ 个节点的连通分量，那么您已经找到了您要查找的边。如果您使用 union-find 数据结构的快速实现，这将在时间 O(n + mα(n)) 内运行，这在实践中基本上是线性的。