【模板】點雙連通分量、橋連通分量、強連通分量（BCC & SCC）
===
## DFS Tree
DFS Tree 是將一張圖 DFS 之後構成的一顆樹。
### 有向圖的 DFS Tree
我們考慮 DFS 一張有向圖，在 DFS 途中，若通過 $u \to v$ 從 $u$ 走到鄰居 $v$，可能有以下情況：
1. Tree Edge：若 $v$ 尚未被造訪過，則會繼續從 $v$ DFS 下去，且 $u \to v$ 為 Tree Edge。而這些邊也就是是在 DFS 過程中實際有走的邊。
當 DFS 結束，Tree Edge 會把所有點連成一顆樹。而剩下的邊便是在 DFS 過程中，某些節點會連向已造訪的節點，所以沒有 DFS 下去的那些邊。分成三種：
1. 若 $v$ 被造訪過，且 $v$ 為 $u$ 在 DFS Tree 上的祖先。此時 $u \to v$ 為 Back Edge。
2. 若 $v$ 被造訪過，且 $v$ 為 $u$ 在 DFS Tree 上的子孫。此時 $u \to v$ 為 Forward Edge。
3. 若 $v$ 被造訪過，但 $v$ 不屬於以上情況，為其他分枝的節點。此時 $u \to v$ 為 Cross Edge。
### 無向圖的 DFS Tree
而在無向圖中，只存在 Tree Edge 和 Back Edge。
我們考慮 DFS 一張無向圖。如果在從 $u$ 走到 $v$ 時， $v$ 尚未造訪過，那麼會繼續從 $v$ 探訪下去，此時 $u \to v$ 為 Tree Edge。反之若 $v$ 已經造訪過，就不會探訪下去——此時 $u \to v$ 為 Back Edge。
DFS 完成之後，Tree Edge 會形成一張包含所有節點的有根樹。而某些節點，會擁有一條 Back Edge 連回他們在 DFS Tree 上的祖先。
為何無向圖沒有 Forward Edge 或 Cross Edge？在無向圖中 DFS 時，若碰到一鄰居已經參訪過了，那麼他必定還沒有「完成」DFS，也就是該鄰居的 DFS 一定還在 in-stack 的狀態。因此他必定是 DFS Tree 上的祖先。
## 割點與橋 AP & Bridge
假設有一無向圖 $G$，若將一個點 $u$ 拔除後，會使得連通塊數量變多，那麼該點為「割點（Articulation Point）」。若將一條邊 $(u,v)$ 拔除後，會使得連通塊數量變多，則該邊為「橋邊（Bridge）」。
找 AP 和 Bridge 當然可以暴力拔拔看，但我們有 Tarjan 算法可以在 $O(|V|+|E|)$ 的時間找到所有割點與橋。
### Low 函數
我們定義 $d(u)$ 為 $u$ 點在 DFS 過程中獲得的「進入」的時間戳。那麼我們知道，在 DFS Tree 當中，$u$ 祖先的時間戳 $d(ancestor)$ 一定比 $d(u)$ 來得小。
我們再定義 $low(u)$ 為 $u$ 不經由通往 parent 的 Tree Edge 時，所能到達的節點中最小的 $d(v)$。不沿著 Tree Edge 往上走，那麼能到達的點就只有：自己、所有子孫、自己以及所有子孫的 Back Edge 連出去的節點。那麼顯然答案只有自己，或是子樹中 Back Edge 的出度。
因此我們可以這麼轉移： $low(u) = min(low(son_u), d(u), d(b_u)))$。其中 $son_u$ 為 $u$ 所有親兒子，$b_u$ 為所有 $u$ 的 Back Edge 連回去的點。
### Tarjan’s for AP & Bridge
Tarjans 算法基於三個定理：
1. 根節點 $r$ 是 AP $\iff$ $deg(r)>1$
2. $u$ 是非根節點 ， $v$ 是 $u$ 的兒子
$u$ 是 AP $\iff$ $\forall v \, low(v) \le d(u)$
3. $u$ 是非根節點， $v$ 是 $u$ 的兒子
$(u,v)$ 是 Bridge $\iff$ $\forall v \, low(v) < d(u)$
也能用下面的方法判斷橋，跟上面是等價的：
- 若 $u$ 是非根節點，$p$ 是 $u$ 的父親，則：
$(u,p)$ 是 Bridge $\iff$ $low(u)=d(u)$
```cpp
void DFS(int v, int fa) //call DFS(v,v) at first
{
D[v] = L[v] = timestamp++; //timestamp > 0
int childCount = 0; //定理1 for root
bool isAP = false;
for (int w:adj[v])
{
if( w==fa ) continue;
if ( !D[w] ) // D[w] = 0 if not visited
{
DFS(w,v);
childCount++;
if (D[v]<=L[w]) isAP = true; //定理2
if (D[v]< L[w]) edgeBridge.emplace_back(v, w);//定理3
L[v] = min(L[v], L[w]);
}
L[v] = min(L[v], D[w]);
}
if ( v == fa && childCount < 2 ) isAP = false; //定理1, v==fa只是確認root
if ( isAP ) nodeAP.push_back(v);
return ;
}
```
> 練習
**UVa 315，找 AP**
>
## 邊雙連通分量
若一個連通分量裡沒有橋，那他就是一個「橋連通分量」。橋連通分量也稱「邊雙連通分量」。在一張連通無向圖中，我們稱 $u,v$ 是邊雙連通的，若且唯若刪除任何一條邊，$u,v$ 皆保持連通。
邊雙連通有傳遞性，因此每個點洽屬於一個邊雙連通分量。每個橋連通分量之間，會以橋作為連接，橋的兩端分別隸屬不同橋連通分量。我們可以在做 Tarjan 時，從下到上的拔除橋連通分量，求出它們。
在 DFS Tree 中，我們一但發現 $u$ 以及其父親 $p$ 會形成橋邊 $(u,p)$，那們 $u$ 便是一個橋的下端點。由於我們子樹中屬於其他橋連通分量的部分已經被拔除，因此 $u$ 僅存的子樹都和 $u$ 屬於同一個橋連通分量。
我們可以通過前序 stack 來維護子樹節點，具體來說，在初造訪 $u$ 時，把 $u$ 放進 stack。在 $u$ 的子孫走訪結束返回到 $u$，並發現 $u$ 為橋的下端點時，將 $u$ 以及還存在 stack 中的子樹都 pop 出來，這些點就隸屬同一個橋連通分量。
```cpp
void DFS(int v, int fa) { //call DFS(v,v) at first
D[v] = L[v] = timestamp++; //timestamp > 0
st.emplace(v);
for (int w:adj[v]) {
if( w==fa ) continue;
if ( !D[w] ) { // D[w] = 0 if not visited
DFS(w,v);
L[v] = min(L[v], L[w]);
}
L[v] = min(L[v], D[w]);
}
if (L[v]==D[v]) {
bccid++;
int x;
do {
x = st.top(); st.pop();
bcc[x] = bccid;
} while (x!=v);
}
return ;
}
```
## 點雙連通分量
若在一連通無向圖中，我們稱 $u,v$ 是點雙連通的，若且唯若任何一點拔除（不包含 $u,v$），皆不會使得 $u,v$ 不連通。點雙連通不具有傳遞性，因此兩個點雙連通分量可能會共用一個點。
相鄰的點雙連通分量之間以割點做分隔，但是共用割點。因此求點雙連通分量的方法和求邊雙連通類似，在發現割點時將 stack 中剩餘的點 pop 出來，這些點便和該割點同一個點雙連通分量。接著還要再該割點 push 回 stack，因為該割點還會屬於另一個點雙連通分量。
```cpp
stack<tuple<int,int>> st;
void DFS(int v, int fa) { //call DFS(v,v) at first
D[v] = L[v] = timestamp++; //timestamp > 0
for (int w:adj[v]) {
if( w==fa ) continue;
if ( !D[w] ) { // D[w] = 0 if not visited
st.emplace(v, w);
DFS(w,v);
L[v] = min(L[v], L[w]);
if (L[w] >= D[v]) { // 找到割點!
int x, y;
bcc.push_back({});
do {
tie(x, y) = st.top(); st.pop();
bcc.back().emplace_back(y);
} while (tie(x, y) != tie(v, w));
bcc.back().emplace_back(v);
}
}
L[v] = min(L[v], D[w]);
}
return ;
}
```
## 強連通分量
有一有向圖 $G$，我們稱 $u,v$ 是強連通的（Strong Connected），若且唯若存在 $u$ 到 $v$ 的路徑，也存在 $v$ 到 $u$ 的路徑。也就是，在一個有向環裡的節點，都互相是強連通的。強連通具有傳遞性，因此每個節點恰屬於一個強連通分量（Strong Connected Component）
我們可以將一個 SCC 分量縮成一點，那麼新圖一定會是一張 DAG。若新圖存在環，那麼環上的所有節點應該要屬於同一個 SCC 才對。
### Kosaraju’s algo
顯然，一個強連通分量的反圖也是一個強連通分量。有一圖 $G$，假設從起點 $r$ DFS 可以走到所有點，那麼使用後序將節點放進序列：若序列裝 $u$ 在 $v$ 前面，代表 $v$ 在 $G$ 中可以通往 $u$。
使 $rG$ 為 $G$ 的反圖。接著從序列的後往前遍歷（以 $u$ 表示），那麼在 $rG$ 中從 $u$ 做起點 DFS，可到達的點在就是在反圖中可以到達（以 $v$ 表示）。若 $v$ 在序列中，排序比 $u$ 前面，則代表 $u, v$ 可以互相抵達，也就是屬於同一個 SCC。
```cpp
void DFS(vector<int> *dG, int v, int k=-1){
visited[v] = true;
scc[v] = k;
for (int w:dG[v])
if (!visited[w])
DFS(dG,w,k);
if(dG==G) st.push(v);
}
int Kosaraju(int N){
memset(visited,0,sizeof(visited));
for(int i=0; i<N; ++i) if(!visited[i]) DFS(G,i);
memset(visited,0,sizeof(visited));
while(!st.empty()){
if (!visited[st.top()]) DFS(GT, st.top(), sccID++);
st.pop();
}
return sccID;
}
```
> 練習題：
**Luogu 2863**
>
## 圓方樹
## Reference
- [https://slides.com/sylveon/graph-7](https://slides.com/sylveon/graph-7#/3/14/6)
- 這裡寫了差分求 AP & Bridge 的方法：https://oi-wiki.org/graph/bcc/
- 程式碼：sylveon
Sign in with Wallet
Connect another wallet