分解的图算法

Question

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

因此，在边列表中有一个特定的边，因此在移除它之前，有一个连接的组件的顶点数超过 n/4 个顶点的底部。移除此边后，图中没有连接组件的顶点数超过 n/4 个顶点的底部。

我将如何设计找到这条边的最佳算法。我是否只是开始删除边，然后每次遍历图以检查最大的连通分量是否足够？这在O（nm）时间内运行，但我觉得一定有更快的方法。我认为答案与使用脱节集来找到连通分支有关，但我不确定如何实现它。

Answer 1

考虑反向运行此过程，添加边而不是删除边。该过程与Kruskal算法非常相似（每个节点都从自己开始，并且在连接不同连通分支的过程中添加边），只是一旦至少有一个连接组件中至少有n/4节点，您就会停止。

解决这个问题的一种方法是使用Kruskal算法的修改版本和增强的联合查找数据结构，以便联合查找结构中的每个代表存储其连接组件中的节点数。按相反顺序遍历边，如果endpoint已连接，则在每个点处丢弃边，否则将链接边。如果添加的边导致存在至少一个的连接组件⌊n/4⌋ 节点，你已经找到了你要寻找的边。如果使用union find数据结构的快速实现，这将在时间O（n mα（n））内运行，在实践中基本上是线性的。