割點 Tarjan 演算法

發表於 分類於 閱讀次數： Waline： 文章字數： 756

最近學習圖論，寫篇題解記錄一下。

定義

  • 對於一個無向圖，如果把一個點刪除後這個圖的極大連通分量數增加了，那麼這個點就是這個圖的割點（又稱割頂）。

這篇部落格主要介紹，Tarjan 演算法用於求 割點。

割點

Tarjan 演算法，記錄 節點訪問時間戳 dfn，節點能夠回溯到的最早的點的時間戳 low。

對於某一點： 1. 如果這個點是根節點，且有兩個以上與它相連的連通分量，那這個點就是割點。 2. 如果某個點後繼是一個連通分量，而這個點不是根節點，那這個點是割點。

第一種情況

我們需要記錄根節點 fa，在遍歷的時候，如果重複訪問到了 fa，說明找到了 fa 下面的一個連通分量。

第二種情況

設當前點 s，對於訪問的下一個節點 y：

如果 low[y] >= dfn[s]，說明這個點下面有一個連通分量。

注：這裡類似於 Tarjan 求 SCC 時，我們所做的 min(low[s],dfn[y])。

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void tarjan(int s, int fa){
    dfn[s] = low[s] = ++cc;
    int child = 0;
    for(int i = head[s]; i!=-1; i=NDS[i].next){
        int y = NDS[i].to;
        if(!dfn[y]){
            tarjan(y,fa);
            low[s] = min(low[s], low[y]); // 回溯後更新
            if(low[y]>=dfn[s] && s != fa) // 情況 2
                cut[s] = 1;
            if(s==fa) // 情況 1 計數
                child++;
        }
        low[s] = min(low[s], dfn[y]);
    }
    if(child>=2&&s==fa){
        cut[s] = 1; // 情況 1
    }
}