图有 n 个顶点和 m 个边。图形开始连接，然后按照边在列表中出现的顺序删除边。在该过程结束时，图表将断开连接。
因此，边列表中有一条特定的边，因此在删除它之前，有一个连接组件的顶点数超过 n/4 层。删除这条边后，图中不存在超过 n/4 个顶点的连通分量。
我将如何设计最佳算法来找到这个边缘。我是否只是开始删除边缘，然后每次遍历图形以检查最大的连接组件是否足够？这在 O(nm) 时间内运行，但我觉得必须有一些更快的方法。我认为答案与使用不相交的集合来查找连接的组件有关，但我不确定如何实现它。
最佳答案
考虑反向运行此过程，添加边而不是删除边。该过程与 Kruskal 算法非常相似(每个节点都从自身开始，并在连接不同的连接组件时添加边)，只不过一旦存在至少一个具有至少 ⌊n/4⌋ 的连接组件，您就停止其中的节点。
解决这个问题的一种方法是使用 Kruskal 算法的修改版本和增强的并查找数据结构，以便并查找结构中的每个代表存储其连接组件中的节点数。以相反的顺序遍历边，如果端点已连接，则在每个点丢弃该边，否则将它们链接起来。如果您添加的边导致存在至少 ⌊n/4⌋ 个节点的连通分量，那么您就找到了您正在寻找的边。如果您使用并查数据结构的快速实现，这将在 O(n + mα(n)) 时间内运行，这在实践中本质上是线性的。
关于algorithm - 图算法拆解，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/42837833/