對「Union and find」的反向操作

Question

我們知道有「聯合並找到」不相交的集合。 http://en.wikipedia.org/wiki/Union_find

但是如何做反向操作呢？考慮一個N節點與E邊相連的集合（實際上是一個圖）。 在每一步我們都想刪除一些邊，並檢查這個刪除操作是否導致另一個不相交集。是否有可能像在「聯盟和發現」中一樣快速地做到這一點？

P.S這不是功課，我們有假期:)

Answer 1

這被稱爲在線邊緣缺失問題或在線連接問題。一些鏈接算法在這section of the Wikipedia article on graph connectivity。

Answer 2

所以你的問題是如何有效檢測Bridge？這可以在線性時間內完成（另請參閱鏈接）。

Answer 3

在Kruskal算法中使用聯合查找，該算法重複添加不構成循環的最小權重邊。在reverse-delete algorithm中使用了一個相反的想法 - 只要它不斷開圖形就消除最大權重的邊緣，這似乎可以利用一些複雜的數據結構（參見Wikipedia）。