連接組件數

Question

我試圖解決以下圖表問題：

我們一般給出一個加權和無向圖和K（K < | V |）是 已經頂點事先已知。頂點被順序刪除。每次刪除 後，有多少個連接組件？

我想用的Tarjan的算法在每一步檢查，如果當前頂點被刪除是割點，從而進行了刪除的時候，我們可以簡單的鄰居的號碼添加到連接組件的數量。該算法的複雜度爲O（V（V + E））。

有人告訴我，有一個O（V + E）算法來執行此任務。但我無法弄清楚。谷歌的研究也沒有透露太多。任何人都可以請教我嗎？

Answer 1

我們可以使用事先知道頂點的事實。我們來解決一個「反向」問題：給定一個圖表和一個列表頂點，它們被順序地加到它上面，在每個加法結構之後計算圖中連接的組件的數量。

該解決方案非常簡單：我們可以維護一個不相交集合並結構，並將所有入射到頂點的邊添加到圖中（這很容易保持此結構中的組件數量：最初，它等於數當實際發生聯合時，減少1）。

原來的問題歸結爲「反向」一個以下列方式：

1. 讓我們補充說，沒有入射到任何要刪除的頂點到分離集工會的所有邊緣。

2. 現在我們可以反轉已刪除頂點的列表，並按上面所述逐個添加它們。

3. 之後，我們需要反轉包含組件數量的結果列表。

注：該解決方案是不實際O(V + E)，其O(V + E * alpha(V))，其中alpha(x)是逆阿克曼的功能。對於所有實際目的而言，它非常接近線性。