給定一個連通圖 G 和一系列邊 S。一次一條，從 G 中洗掉一條來自 S 的邊。然后檢查 G 是否仍然連通。如果 G 不再連接，則回傳邊。否則，您從圖中洗掉邊并繼續。
我最初的想法是使用 Tarjan 的橋查找演算法，該演算法構建一個 DFS 樹，然后檢查給定頂點是否具有將其后代之一或其祖先之一連接到它的后邊。如果沒有，那么它就是一座橋梁。
在構建樹時，您可以在 O(V E) 時間內找到所有橋梁，但我在調整 Tarjan 演算法以解決洗掉問題時遇到了問題。每次洗掉一條邊時，樹都會發生變化，我無法將演算法保持在 O(V E) 時間。有什么想法嗎？
uj5u.com熱心網友回復：
您可以在幾乎線性的時間內相當容易地做到這一點O(E * alpha(V))，其中 alpha 是可笑地緩慢增長的逆阿克曼函式，使用不相交集資料結構。訣竅是反轉S和添加邊，因此您詢問何時G首次連接，而不是斷開連接。增量連通性問題比遞減連通性問題要容易得多。
給定一個不相交集的實作，您可以對其進行擴充以跟蹤組件的數量，并且當只有一個組件時，圖是完全連接的。如果你從n組件開始，那么在任何Union(x, y)操作之前，檢查是否x和y屬于同一個組件。如果他們不這樣做，那么聯合操作會將圖的組件減少 1。
對于您的圖表，您需要進行預處理S以找到所有G不在的邊S，然后首先將它們添加到不相交集資料結構中。那么，如果添加S[i]導致圖第一次連接，答案是i，因為我們已經添加了S[i 1], S[i 2], ... S[n-1]。
最優復雜度
逆阿克曼函式最多4適用于適合我們宇宙的任何輸入，因此我們的聯合查找演算法通常被認為是“幾乎是線性的”。但是，如果這還不夠好...
您可以在 中執行此操作O(V E)，盡管它非常復雜，并且可能主要是理論上的興趣。Gabow 和 Tarjan 在 1984 年的論文中發現了一種演算法，O(1)如果我們知道所有聯合操作的順序，則該演算法支持在每個操作的攤銷成本中進行聯合查找，我們在這里執行此操作。它仍然使用不相交集資料結構，但添加了額外的輔助結構來快取小集上的節點資訊。
論文中提供了一些偽代碼，但您可能需要自己實作或在線查找實作。它也只適用于單詞 RAM model，因為它從根本上依賴于在恒定時間內操作小位串以將它們用作查找表（一個相當標準的假設，但您需要進行一些低級位操作）。
uj5u.com熱心網友回復：
Find the bridge edges
FOR E in S
IF E is a bridge
STOP
remove E
IF E1 is disconnected ( zero edges on E1 )
STOP
IF E2 is disconnected
STOP
E1 和 E2 是由 E 連接的頂點
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/424315.html
上一篇：使用遞回的int陣列的排列