最近學習圖論，寫篇題解記錄一下。
定義
- 對於一個無向圖，如果把一個點刪除後這個圖的極大連通分量數增加了，那麼這個點就是這個圖的割點（又稱割頂）。
這篇部落格主要介紹，Tarjan 演算法用於求 割點。
割點
Tarjan 演算法，記錄 節點訪問時間戳 dfn，節點能夠回溯到的最早的點的時間戳 low。
對於某一點：
- 如果這個點是根節點，且有兩個以上與它相連的連通分量，那這個點就是割點。
- 如果某個點後繼是一個連通分量，而這個點不是根節點，那這個點是割點。
第一種情況
我們需要記錄根節點 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)
cut[s] = 1;
if(s==fa)
child++;
}
low[s] = min(low[s], dfn[y]);
}
if(child>=2&&s==fa){
cut[s] = 1;
}
}
|
