###### tags: `CP`

# [CP] Strongly Connected Components
reference：[programiz](https://www.programiz.com/dsa/strongly-connected-components)

----
想要找出圖上的所有強連通分量(假設圖是一個連通圖)(沒有節點是出入度都為0)，可以使用Kosaraju's algorithm，用時$O(V+E)$來找到，算法步驟非常簡單。
1. DFS一次，並且記錄每一個節點的離開時間。
- 這邊要特別注意的是，紀錄的是離開時間，而我們實作的方式是利用stack紀錄進入時間，這樣在出棧的時候的順序就是離開時間
2. 建立一張反圖 $G^T$(把所有邊反過來)
$e(i, j) \in G \to e(j, i) \in G^T$
3. 根據stack出棧的順序，在反圖上DFS，如果搜到山窮水盡，就是一個SCC

vt<vt<ll>> G, rG, SCC;
vt<ll> vis, comp;
stack<ll> sta;
void dfs_fill(ll x) {
    //if (vis[x]) { return; }
    for (auto& e : G[x]) {
        if (!vis[e]) {
            vis[e] = 1;
            dfs_fill(e);
        }
    }
    sta.push(x);
}
void dfs_find_SCC(ll x) {
    comp.push_back(x);
    for (auto& e : rG[x]) {
        if (!vis[e]) {
            vis[e] = 1;
            dfs_find_SCC(e);
        }
    }
}
void print_stack(stack<ll> a) {
    stack<ll> b = a;
    while (b.size()) {
        ll x = b.top(); b.pop();
        cout << x << " ";
    }
    cout << endl;
}
void solve() {
    const int n = 8;
    G.resize(n);
    rG.resize(n);
    vis = vt<ll>(n, 0);
    G[0] = { 1 };
    G[1] = { 2 };
    G[2] = { 3,4 };
    G[3] = { 0 };
    G[4] = { 5 };
    G[5] = { 6 };
    G[6] = {4,7};

    for (ll i = 0; i < n; ++i) {
        for (ll j = 0; j < G[i].size(); ++j) {
            ll u = i, v = G[i][j];
            rG[v].push_back(u);
        }
    }
    vis[0] = 1;
    dfs_fill(0);
    for (ll i = 0; i < n; ++i) { vis[i] = 0; }
    while (sta.size()) {
        ll v = sta.top(); sta.pop();
        if (vis[v]) { continue; }
        vis[v] = 1;
        dfs_find_SCC(v);
        SCC.push_back(comp);
        comp.clear();
    }
    for (auto& e : SCC) {
        cout << "{";
        for (auto& v : e) {
            cout << v << " ";
        }
        cout << "}" << endl;
    }
}

實作上也非常容易，基本上就是DFS，效率也夠高。

## 說明：
強連通分量(SCC)在反圖上也是強連通分量(SCC)，但SCC間的邊的方向卻會相反，我們可以透過這個性質去紀錄當時最後離開的節點，也就是原本圖的起點，在反圖上會是最後一個點(如果把SCC視為一個頂點)，但這時候因為是反圖且圖是有向的，沒有辦法利用邊搜到下一個SCC，因此就搜到山窮水盡，就是這個SCC了，接著就可以把這個SCC標記，去搜下一個!