algorithm - 如何动态查找连通分量

Question

利用disjoint-set数据结构可以轻松得到Graph的连通分量。而且，它只支持 Incremental Connected Components .

但是，在我的例子中，删除边非常常见，因此我正在寻找一种算法或新结构可以完全动态地(包括添加和删除边)维护连接组件

谢谢

Answer 1

Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity (Holm, de Lichtenberg and Thorup 2001)给出了一种算法，允许任意顺序的边插入、删除和连接查询，更新(插入和删除)需要 O(log(n)^2) 摊销时间，查询需要 O(log(n)/log(log (n))) 时间，其中 n 是图中的顶点数。这些时间范围假设图形开始时没有边。

我只浏览了它 38 页中的前 2 页，但不要(太)害怕——这篇论文描述了一堆关于动态图的新算法(也就是说，可以随着时间的推移进行有效修改)其中连接性最简单。