在圖形中長時間檢測節點的連通性

我從一個沒有邊的N節點開始。在圖形中長時間檢測節點的連通性

然後我開始採取M預定步驟。

在每一步中，我必須在兩個節點之間創建一條邊，或者刪除一條邊。

每一步之後，我必須打印出圖中有多少連接組件。

有沒有一種算法來解決這個問題的時間線性關於M？如果不是，在最壞的情況下，有沒有比O(min(M,N) * M)好？

編輯：

該計劃沒有得到決定M步驟是什麼。

我必須從輸入中讀取，我是否應該創建邊或刪除它，以及我應該創建/刪除哪條邊。

所以例如輸入可能是

N = 4 
M = 4 
JOIN 1 2 
JOIN 2 3 
DELETE 2 3 
DELETE 1 2

那麼我的輸出應該是

3 # (1 2) 3 4 
2 # (1 2 3) 4 
3 # (1 2) 3 4 
4 # 1 2 3 4

來源

2014-05-09 math4tots

我不確定我是否正確理解了你，但是你可以使用第一個n-1邊來連接圖，然後剩下的來填充缺少的邊，如果你還沒有用完所有M步那麼，只需重複（刪除1條邊，添加1條邊），直到用完所有M步？ –

@ G.Bach在問題中，您無法選擇「M」步驟。他們是由一些輸入預先確定的。 – math4tots

您是否有權訪問整個查詢序列？ –

有一些方法可以完全在線解決這個問題，但他們比這個回答更爲複雜。我建議的算法是維護可用邊的生成樹，以及生成樹的組件數（以及圖）。如果我們在線完全攻擊這個問題，那麼這會有問題，因爲跨越邊緣的森林邊緣可能會被刪除，留下我們通過未使用的邊緣進行爪子替換。但是，我們知道，圖中當前的每條邊將被刪除。

我們維護的特定跨越森林是最大權重跨越森林，其中每個邊的權重是其刪除時間。如果屬於該生成森林的邊緣被刪除，則不存在替換，因爲連接由其端點表示的組件的其他邊緣尚未被插入，或者權重較小的邊緣已被刪除。

由於Sleator和Tarjan，有一個動態樹數據結構，也被稱爲鏈接/剪切樹，可以在對數時間內提供以下操作。

Link(u, v, w) - inserts an edge between u and v with weight w; 
       u and v must not be connected already 

Cut(u, v) - cuts the edge between u and v, if it exists; 
      returns a boolean indicating whether an edge was removed 

FindMin(u, v) - finds the minimum-weight edge on the path from u to v 
        and returns its endpoints and weight; 
       returns null if either u = v or u and v are not connected

爲了維護森林，從u到v的邊緣插入時，其清除時間比從u到v的路徑上最小，若最低不存在，然後將邊緣。如果最小值小於新邊，則刪除最小值並將其替換爲新邊。否則，什麼都不要做。當從u到v的邊被刪除時，嘗試從森林中刪除它。

這種方法的運行時間是O（m log n）。如果你沒有一個方便動態的樹，那麼它肯定會需要很長時間才能實現。我沒有使用合適的動態樹，而是用一個簡單得多的數據結構取得了成功，該數據結構只將森林存儲爲具有權重和父指針的一堆節點。運行時間是O（m d），其中d是圖形的最大直徑，如果幸運的話，d比n小很多。

來源

2014-05-09 14:43:30

在圖形中長時​​間檢測節點的連通性

回答

相關問題

在圖形中長時間檢測節點的連通性