增量計算圖中的網橋

Question

我試圖解決網上法官的問題。給定一個n個頂點的無向圖（< = 50000），最初沒有邊，然後給出m個邊（<100000），並且我們被要求在每次加法後輸出bridges的數量。時間限制是2秒。我知道在O（N + M）中運行的橋尋找算法，以及我的直接O（M *（N + M））超出預期。有人可以幫助我一個合適的算法？

謝謝。

Answer 1

島是一個節點的集合，這樣你就可以從一個節點遍歷到另一個節點而不會跨越任何橋。沒有連接到任何其他節點的單個節點是島。

島鏈是由橋樑連接的一系列島嶼。島鏈是無環的;如果你通過一座橋離開一個島，除了同一座橋，你不能回到島上。請注意，這與組成島鏈節點的集合是非循環的並不相同;個別島嶼可能包含循環。

當添加的邊緣圖表，遵循這些原則，讓你的鏈條，島嶼，橋樑的軌道：

1. 如果一個新的邊緣補充說，一個島嶼連接到本身，即邊緣不是一座橋。橋樑總數保持不變。

2. 如果兩個島嶼是不一樣的島鏈的一部分，一個新的邊緣添加連接它們，那麼邊緣變成一座橋，這兩個島鏈合併成一個單一的島鏈。

3. 如果兩個島嶼是島鏈的一部分，並且增加了連接它們的新邊緣，則必須合併一些島嶼以維護非循環屬性。通過連接兩個島嶼的島鏈尋找路徑。對於以這種方式遍歷的所有島嶼，包括兩端的島嶼，將它們全部合併成一個島嶼。你以這種方式穿過的任何橋樑都不再成爲橋樑。

通過這些步驟，您可以在添加邊緣的同時保持圖形中橋接的數量。從未連接的節點開始。每個節點都是一個島鏈，其中包含一個島，其中包含一個節點。當您添加邊緣時，請參閱上面的三條規則以根據需要合併島嶼和島嶼鏈。

島可以表示爲一組節點，島鏈可以表示爲島的無向非循環圖。算法中最昂貴的部分是找到兩個現有島之間的路徑;直覺上，我猜測鏈中的島數會相對於n保持較小，因此總體複雜度將接近O（m）時間。