# Tarjan 的連通塊演算法
Tarjan 提出過很多圖論演算法，其中作知名的莫過於最各種連通塊的東西。這篇會提及如何使用 Tarjan 的想法找出圖中的橋連通塊、雙連通塊與強連通塊。這些演算法都會用到 DFS tree 的性質，有興趣可以去[這篇](https://hackmd.io/@ShanC/dfs-tree)複習一下
此外要另外題的就是 Connected Component 有很多種翻譯方式 (e.g. 連通分量、連通成分、連通單元......)，我這邊採用的是「連通塊」這個翻譯，因為這樣可以少打一個字
## 複習 : DFS Tree
### 各種 Edge
有關於什麼是 DFS tree 的結構還有一些名詞，可以複習[這邊](https://hackmd.io/@ShanC/dfs-tree)。這邊就簡單帶過
- {樹邊|tree edge}: 在 DFS tree 的邊
- {後向邊|back edge}: 使樹上後代連回祖先的非樹邊
- {前向邊|forward edge}: 使樹上祖先連到後代的非樹邊
- {交叉邊|cross edge}: 連結兩棵不同子樹節點的非樹邊，兩點沒有血緣關係
### 時間戳記
有關時間戳記還有他們的性質我在[這篇](https://hackmd.io/@ShanC/bfs_dfs#%E6%99%82%E9%96%93%E6%88%B3%E8%A8%98)講過了，有興趣可以去複習。這邊就稍微代個名詞
- $\text{dfn}[~]$ : 紀錄每個點的發現時間
```cpp=
int timmer = 0;
int dfn[MXN]; // 初始化為 0
void dfs(int u) {
dfn[u] = ++timmer; // 紀錄發現時間
for (int &v : g[u]) {
if (!dfn[v])
dfs(v);
}
}
```
以上就是找 $\text{dfn}[~]$ 的程式碼
## 名詞定義
以下介紹橋、關節點與各種連通塊的定義。可以想像如果你開一個轟炸機，要轟炸一些地方使得彼此不連通，那需要轟炸哪裡比較好? 其實這些名詞都是在探討這些東西
### 強連通塊 Strongly Connected Components
「強連通」是一個對於有向圖的形容詞，意思是對於圖上任意兩點都可以互相走到彼此。強連通塊就是極大的強連通子圖，也簡稱 SCC
<center>
圖源 : [台師大演算法筆記](https://web.ntnu.edu.tw/~algo/ConnectedComponent.html)
</center>
### 橋 Bridge
給一張連通無向圖 $G$，若一條邊 $e$ 被刪去後會使圖被分成兩個連通塊，則 $e$ 稱為 bridge。其實就是 cut vertex
<center>
</center>
如上圖，紅色邊就是 bridge。可以是著拔邊看看是否會符合定義
### 橋連通塊 Bridge-connected Component
拔掉所有 bridge 後所形成的連通塊，就稱為橋連通塊，簡稱 BCC
<center>
</center>
如上圖，每個顏色圈起來的就是一個橋連通塊
### 橋的一些性質
#### 環上沒有橋
因為環上割掉任一邊都還是會連通，因此不存在 bridge
<center>
</center>
#### 橋必在每棵生成樹上
[生成樹](https://hackmd.io/@ShanC/minimum-spanning-tree#%E7%94%9F%E6%88%90%E6%A8%B9-Spanning-Tree)就是包含原圖所有節點的最小連通子圖，當然也是一棵樹。其中，由於 bridge 是連接兩個橋連通塊、不可分割的一條邊，因此也定會存在每棵生成樹上，否則不連通
<center>
</center>
上圖為其中一種生成樹，可以發現確實包含所有 bridge (綠色)，而且就算是換成其他生成樹，也只是選出另一條虛線邊、拔掉另一個黑色邊而已，這凸顯 bridge 在生成樹中無可取代的地位
### 關節點 Articulation Vertex
在一個連通圖 $G$ 中，若刪除某節點 $v$ 及其相連的邊，使得連通塊數量增加 (不一定 $+1$)，則 $v$ 為一個關節點。其實就是 cut-vertex
注意到下圖 $x$ 就是關節點:
<center>
</center>
再舉個例子
<center>
</center>
綠色的邊是 bridge，紅節點是關節點，注意到 :
- 只要 bridge 連接的是兩個大小 $>1$ 的連通塊，那麼該 bridge 兩終點都會是關節點
- 因為切掉 $\deg=1$ 的節點不會分割整張圖，因此他不是關節點
- 刪除關節點後會行成的連通塊數量可能很多，像圖中某個關節點刪除後就會形成 $3$ 個連通塊
### 雙連通塊 Biconnected Component
這邊定義稍微繞一點
雙連通塊就是一個不會產生關節點的極大子圖，也就是說刪去任一個點，該子圖仍連通，有時又稱 block 或是 2-connected component，也簡稱 BCC
<center>
</center>
上圖被我畫的很亂，抱歉抱歉
### 注意
- 有橋就**一定**有關節點 (終點 $\deg$ 不為 $1$ 的情況下)
- 有關節點**不一定**有橋
- 再次強調，強連通塊是 for 有向圖，雙連通、橋連通塊是 for 無向圖
- 沒事別用 BCC 這個簡稱，會搞混
如果沒注意到就多注意一點
## 尋找橋
要討論橋，那圖必須是**無向圖**，以下的圖都是無向圖
### 觀察 : 什麼圖不存在橋
根據定義，若拿掉橋，則整張圖會變得不連通。反之，若圖不存在橋，則拿掉任一條邊圖還是會連通，那圖其實就會有個環
<center>
不存在橋的圖
</center>
根據我們在 [DFS tree](https://hackmd.io/@ShanC/dfs-tree) 中的觀察，無向圖測環只需要找 back edge
### 觀察 : bridge 在 DFS tree 中扮演的角色
這邊列舉幾個 bridge 在的性質
#### bridge 在 DFS tree 中一定是 tree edge
若不是 tree edge，那代表一定存在另一條 tree edge 使得原本兩終點連通，但這與 bridge 的性質矛盾，所以不可能
而且 DFS tree 也是一棵生成樹，根據[前面](#橋必在每棵生成樹上)所述，bridge 必備包含在任一生成樹裡面
#### 什麼樣的 tree edge 不是 bridge?
透過觀察，可以知道若有一條 tree edge $u\to v$ 是 bridge，那 $u\to v$ 肯定不存在環上。也就是說 $u,v$ 的子代不會連回去 $u$ 跟的祖先 (包含自己)
<center>
不是 bridge 的情況
</center>
所以我們也可以發現，如果有環產生，但是在 $v$ 的子代且沒有連回去 $u$ 的祖先 (含 $u$)，那 $u\to v$ 仍是一條 bridge
<center>
 
是 bridge 的情況 (左邊有環，右邊沒有)
</center>
### 想法
#### 要處理的問題
要判斷「無向圖中哪條邊是 bridge ?」，根據以上的觀察，對於邊 $(u,v)$ 我們需要處理三個 case :
- 非 tree edge
- 那就一定是 back edge，肯定不是 bridge，因為 bridge 一定是 tree edge
- 是 tree edge
- 如果 $(u,v)$ 是在某個環上，i.e. $v$ 的後代存在一條 back edge 連回去 $u$ 或 $u$ 的祖先，則 $(u,v)$ 不是 bridge
- 若 $(u, v)$ 不在某個環上，那 $(u,v)$ 就是 bridge
#### 要維護的東西
首先要先知道每個節點 $v$ 的發現時間 $\text{dfn}[v]$。為了知道每條邊是不是在某個環上，Tarjan 的演算法中維護了一個很妙的陣列 :
$\text{low}[u]$ : 透過最多一條 back edge，所能到達的節點的最小時間
#### 舉些例子 :chestnut:
如果圖是無環圖 (就是 tree)，那麼每條邊都是 bridge
<center>
</center>
如上圖，因為樹沒有 back edge，所以每個節點的 $\text{low}[~]$ 就是他自己
如果有環的話，可能會向下圖醬
PS : 這裡為了方便，節點編號跟 $\text{dfn}$ 相同
<center>
</center>
在上圖中，當我們拜訪到 $(1,5)$ 那條邊的時候會發現那條邊是 back edge，$5$ 能利用 back edge 到達的最小 $\text{dfn}$ 是 $1$。接下來當 $5$ 成為黑點的時候回傳到 $4$，$4$ 的 $\text{low}$ 也會被更新成 $1$ ...\... 以此類推
#### bridge 的 $\text{dfn}$ 與 $\text{low}$
如果一條邊 $u\to v$ 是 bridge，根據上面觀察，會有以下不等式 :
$$\text{dfn}[u] < \text{low}[v]$$
因為 $v$ 的子代不存在一條 back edge 回到 $u$ 的頭上，因此 $\text{low}[v]$ 一定比較大
### 實作程式碼
這裡來講一下變數好了
- $\text{g}[~]$ : 鄰接陣列
- $\text{timmer}$ : 計時器!!
- $\text{dfn}[~]$ : 發現順序 (時間)
- $\text{low}[u]$ : 從 $u$ 或其子樹節點出發，透過最多一條回邊，所能到達的最小 $\text{dfn}$ 值
- $\text{bridges}[~]$ : 存 bridge 的陣列，裡面包一個 `Edge` 的 struct
因為圖是無向圖，因此 DFS 時需要維護父節點，並且在探索子代時忽視到父節點的邊
```cpp=
vector<int> g[MXN];
int timmer = 0;
int dfn[MXN], low[MXN];
struct Edge { // 就是紀錄邊的 struct
int u, v;
};
vector<Edge> bridges;
void dfs(int u, int p = -1) {
dfn[u] = low[u] = ++timmer;
for (int &v : g[u]) {
if (v == p) continue;
if (dfn[v]) { // 這個點走過
low[u] = min(low[u], dfn[v]); // 那這就是 back edge :D
} // 所以就要更新
else { // 沒走過的點 -> 繼續拜訪
dfs(v, u);
low[u] = min(low[u], low[v]); // 更新 low[u]
if (dfn[u] < low[v]) // 若子節點 low 大於自己
bridges.push_back({u, v}); // 則這就是 bridge
}
}
}
```
提醒 : 在第 $20$ 行，我們必須等子節點是黑點的時候才能判斷
## 找橋連通塊
### 想法
其實就跑兩次 DFS，第一次找 bridge，然後把兩終點分別標上編號。第二次找橋連通塊，看到未編號就標上相同編號、看到不同編號就停下來
### 實作程式碼
整個程式碼分兩階段進行 :
- 第一階段 : 找 bridge
- 第二階段 : 分群找橋連通塊
為了效率，通常會把橋存在一個 set
```cpp=
vector<int> g[MXN];
int timmer = 0;
int dfn[MXN], low[MXN];
set<Edge> bridges;
// 第一階段
void dfs1(int u, int p = -1) {
dfn[u] = low[u] = ++timmer;
for (int &v : g[u]) {
if (v == p) continue;
if (dfn[v]) {
low[u] = min(low[u], dfn[v]);
}
else {
dfs1(v, u);
low[u] = min(low[u], low[v]);
if (dfn[u] < low[v])
bridges.insert({u, v}); // 配合 set 改 insert
}
}
}
// 第二階段
int idx[MXN];
void dfs2(int u, int id) {
idx[u] = id;
for (int &v : g[u]) { // 已分群或是遇到 bridge 就別走
if (idx[v] || bridges.count({u, v}) || bridges.count({v, u}))
continue;
dfs2(v, id);
}
}
// 該寫在主程式的東西
for (int i = 1; i <= n; i++) {
if (!dfn[i])
dfs1(i);
}
int bcc_cnt = 0; // 橋連通塊編號 (數量)
for (int i = 1; i <= n; i++) {
if (!ebcc_id[i])
dfs2(i, ++bcc_cnt);
}
```
如此一來我們就可以知道每個點在哪個橋連通塊
## 尋找關節點
要討論關節點，那圖必須是**無向圖**，以下的圖都是無向圖
bridge 需要觀察的東西是兩終點，而關節點需要觀察的就只有點本身，相對容易觀察一點
### 觀察 : 環與關節點
根據上面在環的觀察，不免令人好奇，關節點會在環上嗎?
<center>
</center>
會的，注意到 $x$ 是在環上的關節點
### 觀察 : 關節點與 DFS Tree
假設你[已經知道 $\text{low}[~]$](#要維護的東西) 是什麼了，這邊要分幾個 case 來談談 :
- 若 $x$ 在環上 :
- 肯定有至少一條 back edge 連到自己才能形成環，且 $x$ 肯定是這個子 DFS tree 的祖先
$\Rightarrow$ $x$ 的子後代們透過一條 back edge 不會跑去 $\text{dfn}$ 值 $<\text{dfn}[x]$ 的地方
$\Rightarrow$ 對於所有子節點 $v$，$\text{dfn}[x] \le\text{low}[v]$
- 若 $x$ 不在環上 :
- 那麼就不會有 back edge 的問題，只要 $x$ 還有子節點，那肯定是關節點，因為 $x$ 至少連了父節點與子節點。我們也可以直接用剛剛的結論套用 : 對於所有子節點 $v$，$\text{dfn}[x] \le\text{low}[v]$
### 觀察 : 根節點
我們[剛剛](#觀察-:-關節點與-DFS-Tree)觀察到的事情有個瑕疵，就是我們預設了每個節點在 DFS tree 上都有父節點，然而根節點是個例外，因此我們要特別觀察根節點 :
若 $x$ 是根節點，不論是否在環上，只要 DFS 樹上的子節點 $>1$ 就肯定是關節點
<center>
 
左圖 : 根 $x$ 不是關節點、右圖 : 根 $x$ 是關節點
</center>
### 實作程式碼
這裡實作其實跟找 bridge 很像，只是改改判斷而已
- $\text{g}[~]$ : 鄰接陣列
- $\text{timmer}$ : 計時器!!
- $\text{dfn}[~]$ : 發現順序 (時間)
- $\text{low}[u]$ : 從 $u$ 或其子樹節點出發，透過最多一條回邊，所能到達的最小 $\text{dfn}$ 值
- $\text{ans}$ : 存關節點的東西，這裡使用 `set` 是因為可以避免重複
```cpp=
vector<int> g[MXN];
int timmer = 0;
int dfn[MXN], low[MXN];
set<int> ans;
void dfs(int u, int p = -1) {
dfn[u] = low[u] = ++timmer;
int child = 0;
for (int &v : g[u]) {
if (v == p) continue;
if (dfn[v]) {
low[u] = min(low[u], dfn[v]);
}
else {
dfs(v, u);
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u] && p != -1) // 判斷是不是關節點
ans.insert(u); // (for 非根)
child++; // 這裡紀錄有幾個孩子
}
}
if (p == -1 && child > 1) // 判斷根是否為關節點
ans.insert(u);
}
```
要注意這邊因為用 `set` 來存，所以複雜度最差會多一個 $\log$
當然，你可以改這邊的東西
注意 : 這裡 DFS tree 上的子節點數量 $\neq$ $\deg$，因為 DFS tree 會排除 back edge 還有連回父節點的邊
## 找雙連通塊
### 回溯
會發現在找到關節點的時候，其實我們已經拜訪完整個雙連通塊了。因此可以利用 DFS 的性質來回溯整個雙連通塊的節點
### 實作程式碼
這裡都跟剛才一樣，只是多了兩個東西 :
- $\text{st}$ : 存點的 stack，以便回溯
- $\text{bccs}$ : 存雙連通塊的點
要注意的是根節點在這不用特別判
還有就是注意下面對於關節點的操作細節
```cpp=
vector<int> g[MXN];
int dfn[MXN], low[MXN], timmer;
stack<int> st; // 存點
vector<vector<int>> bccs; // 存結果
void dfs(int u, int p = -1) {
dfn[u] = low[u] = ++timmer;
st.push(u); // 進入點 u 時 push 進 stack
int child = 0;
for (int &v : g[u]) {
if (v == p) continue;
if (dfn[v]) {
low[u] = min(low[u], dfn[v]);
}
else {
child++;
dfs(v, u);
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u]) { // 當滿足關節點條件時
vector<int> bcc;
int z;
do { // pop 出所有在子樹 v 裡面的點
z = st.top();
st.pop();
bcc.push_back(z);
} while (z != v);
// 關節點 u 本身不彈出，因為它可能屬於其他 bcc
// 我們直接把它加入這個 bcc 集合
bcc.push_back(u);
bccs.push_back(bcc);
}
}
}
}
```
### 找 Bridge?
其實 size 為 $2$ 的雙連通塊就是 bridge，所以也可以直接用這個模板判
但是這本質上還是和橋連通塊不一樣，千萬不要把兩者搞混了，不然就要吃 WA
## 尋找強連通塊
在這邊，SCC 是有向圖才有的東西，所以以下討論都是有向圖
### 觀察 : SCC 在 DFS 樹裡面會形成子樹
根據 SCC 的定義，任意兩點都可以找到一條路徑。所以對於任一個節點也一定可以對所有其他節點找出一條路徑，這樣就形成了一棵樹 (recall 樹的定義)
所以當我們 DFS 完這棵子樹後，$\text{dfn}$ 最小的一定就是根，而且此根的 $\text{low}=\text{dfn}$。因為若 $\text{low}<\text{dfn}$，代表應該有條 back edge 或 cross edge 可以回到更早節點，若 $\text{low}>\text{dfn}$，那就不合理。所以根節點 $\text{low}=\text{dfn}$
### 回溯
跟上找雙連通塊的方法類似，我們可以用回溯的方式找強連通塊
### 判環
要注意的是，在有向圖中，cross edge 或 forward edge 都不會形成環 (當然也不會形成 SCC)，因此只有 back edge 需要判。我們可以用一個陣列來處理這個問題，以下程式碼是利用 $\text{inStack}[~]$ 來處理
### 實作程式碼
原本的變數我懶得寫了，基本都一樣
- $\text{idx}[v]$ : $v$ 是屬於哪個連通塊
- $\text{sccn}$ : SCC 編號
要注意的是，這裡是有向圖，與無向圖寫法有點差異
所以這邊用 $\text{inStack}[~]$ 來維護
```cpp=
vector<int> g[MXN];
int dfn[MXN], low[MXN], timmer = 0;
int idx[MXN], sccn = 0;
bool inStack[MXN];
void dfs(int u) {
dfn[u] = low[u] = ++timer;
s.push(u);
inStack[u] = true;
for (int &v : g[u]) {
if (!dfn[v]) { // 未訪問
dfs(v);
low[u] = min(low[u], low[v]);
}
else if (inStack[v]) { // 環 (是 back edge)
low[u] = min(low[u], dfn[v]);
}
}
if (low[u] == dfn[u]) { // 找到 SCC 的根
sccn++;
while (true) {
int v = s.top();
s.pop();
inStack[v] = false;
idx[v] = sccn;
if (u == v) break;
}
}
}
// 要使用時應該要這樣
for (int i = 1; i <= n; i++) {
if (!dfn[i])
dfs(i);
}
```
這樣就能知道每個節點屬於哪個 SCC 囉
## 後記
### 為什麼要寫這篇呢?
在海大競程學完之後的一年後才自己研究這些東西，為了避免忘記，我寫了這篇筆記，讓自己可以隨時回來複習。因為我們學校競程講義寫得有點糟糕，只把這個演算法當作黑盒子，套用模板而已。Tarjan 的演算法使用非常多 DFS 的性質，可以說沒讀過這些演算法就無法掌握 DFS 的精隨。我是覺得這麼活的東西只套套模板實在是太可惜，這樣解題非常不靈活
### 關於 Tarjan
Tarjan 真的好厲害，把 DFS 玩得淋漓盡致
### 注意到、觀察到
有些證明會幫助理解，有些則比較像是對「數學」這個嚴謹的體系交差而已，不一定會有助於理解。上面提到的「注意到」或「觀察到」應該都是要證明的，只是那樣並不會幫助理解，反而會讓話題失焦，而且這樣的文章我複習起來會看不懂
### 有關參考資料
CP-algorithm 那邊，明明都是用 Tarjan 的概念，但是找 bridge、找關節點與找 SCC，顯然是不同人寫的。符號跟用詞顯然都不一樣，我看的有點燥。台師大的演算法筆記都是用鄰接矩陣，看的時候要稍微翻譯一下變成鄰接串列的版本
### 其他
寫到後面我累了，實作細節講也講不完，反正都看到這裡了，多少對圖論的 code 有點直覺了吧
## 題目練習
[LeetCode 1192. Critical Connections in a Network](https://leetcode.com/problems/critical-connections-in-a-network/description/?envType=problem-list-v2&envId=biconnected-component) (裸題)
[CSES Necessary Roads](https://cses.fi/problemset/task/2076/) (裸題)
[CSES Necessary Cities](https://cses.fi/problemset/task/2077) (裸題)
[CSES Planets and Kingdoms](https://cses.fi/problemset/task/1683/) (裸題)
[CSES Coin Collector](https://cses.fi/problemset/task/1686) (縮點 + DP on DAG)
[2019 ICPC World Finals E. Dead-End Detector](https://codeforces.com/gym/102511/problem/E)
----
## 參考資料
- Introduction to Algorithms, Fourth Edition
- [[Tutorial] The DFS tree and its applications: how I found out I really didn't understand bridges](https://codeforces.com/blog/entry/68138)
- [Wikipedia - Bridge (graph theory)](https://en.wikipedia.org/wiki/Bridge_(graph_theory))
- [Wikipedia - Biconnected component](https://en.wikipedia.org/wiki/Biconnected_component)
- [cp-algorithms - Finding bridges in a graph in $O(N+M)$](https://cp-algorithms.com/graph/bridge-searching.html)
- [cp-algorithms - Finding articulation points in a graph in $O(N+M)$](https://cp-algorithms.com/graph/cutpoints.html)
- [海大競程 - 2023 Advanced Graph Algorithm](https://hackmd.io/@leeshowhaodian/advance_graph#/)
- [台師大演算法筆記 - connected component](https://web.ntnu.edu.tw/~algo/ConnectedComponent.html)
- [Articulation points and bridges (Tarjan's Algorithm)](https://codeforces.com/blog/entry/71146)
- [XDEv11 - 2021 Week12 - Graph (BCC, SCC, LCA)](https://hackmd.io/@XDEv11/NCKU-AdvCP-2021-Graph3)
----
> [ShanC 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC)
> 作者: ShanC
> 更新: 2026/2/15
Sign in via Google
Sign in via Facebook
Sign in via X(Twitter)
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
Connect another wallet