---
tags: codebook, tutorial
---

# Kosaraju

用來求強連通分量 *(Strongly Connected Components)* 的一個演算法

## Steps

設 $G$ 為一個有向圖， $G_r$ 是 $G$ 的反圖(所有邊方向相反)

1. 對 $G$ 做DFS，對途中經過的點後序編號(回傳前由小到大編號)
2. 在 $G_r$ 上用從1. 得到的編號由大到小DFS
每個，所得的每個生成樹都是一個SCC

值得注意的是，得到SCC的順序是一個反向的拓樸排序

## Example

TODO

## Proof

### 1
**證明若 $u, v$ 兩個點在同一個SCC中，兩點會在同一個由 $G_r$ 做DFS產生出來的生成樹上**

因為
$\Rightarrow\exists$ 一條在 $G$ 上，從 $v$ 到 $u$ 及從 $u$ 到 $v$ 的路徑
$\Rightarrow\exists$ 一條在 $G$ 上，從 $u$ 到 $v$ 及從 $v$ 到 $u$ 的路徑

在 $G_r$ 上做DFS的過程中，如果經過了 $u$ ，因為 $u$ 到 $v$ 有路可走，所以會在同一個生成樹上，vice versa

### 2
**證明若 $u,v$ 兩點在 $G_r$ 的同一個生成樹上，兩點會在 $G$ 上的同一個SCC中**

設 $x$ 為包含 $u,v$ 兩點的生成樹的根節點

$\Rightarrow v$ 是 $x$ 的後代
$\Rightarrow\exists$ 一條在 $G_r$ 上，從 $x$ 到 $v$ 的路徑
$\Rightarrow\exists$ 一條在 $G$ 上，從 $v$ 到 $x$ 的路徑 -- (1)

在對 $G_r$ 做DFS時， $x$ 會比 $v$ 先走到 (因為 $x$ 是根節點)

$\Rightarrow$ $x$ 的編號比 $v$ 大 (因為 $G_r$ 的DFS從剩餘的點中編號最大的進行)
$\Rightarrow$ 在 $G$ 的DFS中， $v$ 的遞迴呼叫比 $x$ 早結束 (根據編號可知)

若 $v$ 的DFS遞迴呼叫比 $x$ 早結束，則在對 $G$ 的DFS的時候會有兩種情況

1. $v$ 比 $x$ 先走到
2. $x$ 比 $v$ 先走到

若走到 $v$ 的DFS調用了走到 $x$ 的DFS
$\Rightarrow$ $x$ 的DFS會開始並結束於 $v$ 的DFS結束之前
$\Rightarrow$ $x$ 會比 $v$ 的DFS遞迴呼叫早結束 ***(矛盾)***

若走到 $x$ 的DFS調用了走到 $v$ 的DFS
$\Rightarrow$ $v$ 為 $x$ 的後代
$\Rightarrow\exists$ 一條從 $x$ 到 $v$ 的路徑 -- (2)
$\Rightarrow$ 由 (1)(2) 和證明1 可知 $x$ 和 $v$ 在同一個SCC中

同理可證， $x$ 和 $w$ 在同一個SCC中
$\Rightarrow$ 同理可證 $v$ 和 $w$ 在同一個SCC中

## Implementation

int n; //Vertex amount
V<V<int>> e1(n),e2(n); //G and G_r

V<int> at(n,-1),s;
V<bool> vis(n,false);
V<V<int>> scc;
F<void(int)> kosaraju1=[&]
(int x){
    if(vis[x]) return; 
    else vis[x]=true;
    for(auto& i:e1[x])
        kosaraju1(i);
    s.push_back(x);
};
F<void(int)> kosaraju2=[&]
(int x){
    at[x]=scc.size()-1;
    for(auto& i:e2[x])
        if(!~at[i]) kosaraju2(i);
    scc.back().push_back(x);
};
for(int i=0;i<n;i++)
    kosaraju1(i);
reverse(s.begin(),s.end());
for(auto i:s)
    if(!~at[i]) 
        scc.resize(scc.size()+1),kosaraju2(i);

---

參考資料: https://gtl.csa.iisc.ac.in/dsa/node171.html