# Kosaraju 演算法
此章節接續 [DFS 與 BFS](https://hackmd.io/@ShanC/bfs_dfs)，來聊聊 Kosaraju 演算法是如何運用 DFS 的性質來尋找強連通塊

**在此章節，有時候以 $D$ 代表有向圖 (directed graph)**

## 有向圖的連通性
由於之前講在[連通塊](https://hackmd.io/@ShanC/connected_component)討論的「連通」只適用無向圖。在有向圖中 $G$ 中，$(u, v)$ 與 $(v, u)$ 不見得同時存在，也就是說「$u,v-$路徑」與「$v,u-$路徑」不見得同時存在

### 底圖 Underlying Graph
將一張有向圖的邊 $D$ 改成無向邊，則稱為 $D$ 的「底圖」

<center>
<img src="https://hackmd.io/_uploads/BkBpnc55lg.png" style="width: 200px">
</center>

以上圖為例，左邊是有向圖 $D$，右邊則是 $D$ 的底圖
~~||補充說明: 右邊是著名的 Peterson graph||~~

### 弱連通 Weakly Connected
若一張有向圖 $D$ 的底圖是一張連通圖，則稱 $D$ 是弱連通

### 強連通 Strongly Connected
在一張有向圖 $D$ 中，若所有節點序對 $(u,v)$ 都存在從 $u$ 到 $v$ 的路徑，則稱 $D$ 是強連通

### 強連通塊 Strongly Connected Component
一張有向圖 $D$ 的強連通塊，就是 $D$ 的極大 (maximal) 強連通子圖，簡稱 $\text{SCC}$

digraph{
    node [shape="circle"]
    layout=fdp
    a -> b
    subgraph clusterA{
        a
    }
    subgraph clusterB{
        b
    }
    subgraph clusterC{
        c -> d -> e -> f -> c
        d -> f -> g -> h -> f
    }
    a -> c
    b -> e
}

以上圖為例，共有三個強連通塊: $\{a\},\{b\},\{c,d,e,f,g,h\}$

## Kosaraju's Algorithm 尋找強連通塊

### 運作原理
Kosaraju 演算法是透過拓樸排序的方式，記錄圖 $G=(V,E)$ 中每一個走訪節點的順序。接下來藉由排好的節點順序來走訪逆向連邊的圖 $G^T=(V,E^T)$，如果一條邊的兩點 $u, v$ 是在不同連通塊，可以保證走訪 $G^T$ 時，不會從 $v$ 走到 $u$。因此在 $G^T$ 的 $\text{dfs}$ 樹上，不同連通塊會形成不同的樹

### 運作步驟
1. 利用 $\text{dfs()}$，計算 $G$ 結束每個節點的時間
2. 建立 $G^{T}=(V, E^{T})$
3. 利用 $\text{dfs( )}$ 與先前的計算的結束時間，遍歷 $G^T$ 的所有節點。並在走訪每一個 $\text{dfs}$ 樹的根節點時，分成不同的強連通塊

以下會利用 [DFS 中的定理與性質](https://hackmd.io/@ShanC/bfs_dfs#%E6%99%82%E9%96%93%E6%88%B3%E8%A8%98)，證明這個方法的正確性

### 引理 1
設 $C$ 與 $C'$ 是在有向圖 $G$ 中的不同連通塊，且 $u,v \in C$、$u',v' \in C'$。如果 $G$ 裡有路徑從 $u$ 到 $u'$，那就不會存在一條路徑從 $v'$ 到 $v$

#### 引理 1 證明
透過反證法，如果存在一條路徑從 $v'$ 到 $v$，則 $C$ 與 $C'$ 就會是同一個連通塊，違背了原本假設

digraph{
    node [shape="circle"]
    layout=fdp
    subgraph clusterA{
        label = C
        u -> v -> u
    }
    subgraph clusterB{
        label = C’
        u’ -> v’ -> u’
    }
    u -> u’
    v’ -> v
}

如上圖，路徑 $v'$ 連到 $v$ 會導致存在一條路徑使 $C$ 跟 $C'$ 強連通

### 引理 2
設 $C$ 與 $C'$ 是在有向圖 $G=(V,E)$ 中的不同連通塊，假設有一條邊 $(u,v)\in E$，其中 $u\in C$ 且 $v\in C'$。那麼 $f(C') > f(C)$，即 $C'$ 的完成時間會比 $C$ 晚

#### 引理 2 證明
如果 $d(C') < d(C)$，即 $C'$ 比 $C$ 早發現。設 $x$ 是 $C'$ 裡第一個發現的節點，則根據白路徑定理，$C' - x$ 與 $C$ 中的所有節點都是白色。我們考慮以下兩種狀況:
1. 如果有一條路徑從 $C'$ 到 $C$ ，則在 $\text{dfs}$ 樹中，$C' - x$ 與 $C$ 中的所有節點都是 $x$ 的後代，所以根據括號定裡， $f(x)=f(C') > f(C)$
2. 如果不存在一條路徑從 $C'$ 到 $C$，則在走訪到 $C$ 之前，$C$ 的所有節點都是白色，這意味著 $f(C') < f(C)$，即 $C'$ 比 $C$ 早結束拜訪

得證

### 推論 1
設 $C$ 與 $C'$ 是在有向圖 $G=(V,E)$ 中的不同連通塊，假設 $f(C) > f(C')$，那麼在逆向圖 $E^T$ 裡並沒有一條邊 $(u,v)$ 滿足 $u \in C$ 且 $v\in C'$

#### 推論 1 證明
從引理 2 可得到這個結論

### 證明: Kosaraju's Algorithm 可以找到 $\text{SCC}$
我們使用運作步驟 3 與數學歸納法來證明之:
- 基本情況: 如果還沒開始走訪則還沒有任何連通塊出現
- 歸納步驟: 假設前 $k$ 個 $\text{dfs}$ 樹，每一個都是一個強連通塊，我們考慮產生 $k+1$ 棵 $\text{dfs}$ 樹。假設 $x$ 是這棵 $\text{dfs}$ 樹的根，即強連通塊 $C$ 中第一個發現的節點。若存在非 $C$ 且尚未拜訪的強連通塊 $C'$，則根據引理 2， $f(x)=f(C) > f(C)$。根據假設，在造訪 $x$ 時，$C$ 的其他點都是白色的。因此，根據白路徑定理，$C$ 中其他節點都是 $\text{dfs}$ 樹中 $x$ 的後代。又根據假設及推論 1，在 $G^T$ 中，離開 $C$ 的邊一定都是被造訪過的強連通塊。因此，在深度優先走訪期間，非 $C$ 的任何強連通塊都不是 $x$ 的後代。在 $G^T$ 中以 $x$ 為根的 $\text{dfs}$ 樹的節點正好形成一個連通塊。如此一來便完成了歸納步驟和證明

## 程式實作 Kosaraju's Algorithm
- $\text{vis[ i ]}$ : 紀錄節點 $\text{i}$ 是否被拜訪過
- $\text{edge[ ]}$ : 順向鄰接陣列
- $\text{redge[ ]}$ : 逆向鄰接陣列
- $\text{nscc}$ : $\text{SCC}$ 的數量
- $\text{order[ ]}$ : 結束拜訪的時間順序
- $\text{bln[ i ]}$ : 紀錄第 $\text{i}$ 個節點屬於哪個 $\text{SCC}$
- $\text{n}$ : 節點的數量
- $\text{m}$ : 邊的數量

**此程式碼是 0-based**

bool vis[MXN];
vector<int> edge[MXN], redge[MXN];  // 這兩個在輸入的時候就先維護好
vector<int> order, bln;
int n, m, nscc = 0; // 0-based

void dfs(int u) { // 順向走訪
    vis[u] = true;
    for (int &v : edge[u]) {
        if (!vis[v])
            dfs(v);
    }
    order.push_back(u); // 結束拜訪紀錄
}

void rdfs(int u) { // 逆向走訪
    vis[u] = true;
    bln[u] = nscc;
    for (int &v : redge[u]) {
        if (!vis[v])
            rdfs(v);
    }
}

void kosaraju() {
    bln.resize(n, -1);
    for (int i = 0; i < n; i++) {
        if (!vis[i])
            dfs(i);
    }
    reverse(order.begin(), order.end());
    memset(vis, false, sizeof(vis)); // 因為要再次走訪所以歸零
    for (int &i : order) {
        if (!vis[i]) {
            rdfs(i);
            nscc++; // 每次都加 1
        }
    }
}

## 時間複雜度
設 $n=|V|$、$m=|E|$
- 執行 $\text{dfs( )}$ : $O(n+m)$
- 執行 $\text{rdfs( )}$ : $O(n+m)$
- 總時間複雜度: $O(n+m) + O(n+m) = O(n+m)$

## 題目練習
[CSES Planets and Kingdoms](https://cses.fi/problemset/task/1683/) (裸題)
[CSES Coin Collector](https://cses.fi/problemset/task/1686/) (找 SCC + DP)
[Zerojudge d197. 11504 - Dominos](https://zerojudge.tw/ShowProblem?problemid=d197) (動動腦)
[Zerojudge g554. 周遊列國(Travel)](https://zerojudge.tw/ShowProblem?problemid=g554) (動動腦)
[CSES Giant Pizza](https://cses.fi/problemset/task/1684) (想辦法把邏輯問題轉成圖論問題)
[Codeforces Gym - 102439B Varvara and matrix](https://codeforces.com/gym/102439/problem/B)
[CodeForces - 505D Mr. Kitayuta's Technology](https://codeforces.com/problemset/problem/505/D)
[CSES Flight Routes Check](https://cses.fi/problemset/task/1682) (裸題)

----

## 參考資料
- Introduction To Graph Theory - D. B. West
- Introduction to Algorithms, Fourth Edition
- [graph - 台師大演算法筆記](https://web.ntnu.edu.tw/~algo/Graph2.html)
- [Strongly Connected Components - Geeksforgeeks](https://www.geeksforgeeks.org/strongly-connected-components/)

----

> [ShanC 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC)
> 作者: ShanC
> 更新: 2024/12/8