---
# System prepended metadata

title: 強連通分量 Strongly Connected Component
tags: [note]

---

---
tags: note
---

# 強連通分量 Strongly Connected Component


## 什麼是SCC

在有向圖中，如果一個圖的任意兩點都能互相抵達，則稱該圖是強連通的。

而在一張有向圖中能夠實現強連通的子圖我們稱為強連通分量，如果一個強連通分量滿足「加上任意一個其他的點就不再連通」，那我們會稱這樣的連通元件是「極大的」，通常沒特別提及，我們會默認討論極大強連通分量。

## 怎麼求SCC

### 先備知識

#### DFS生成樹

![](https://i.imgur.com/TDqSyvr.png)


##### tree edge

DFS搜索時連向還沒有訪問過的點的邊

##### back edge

連向祖先節點的邊

##### cross edge

連向已經訪問過但不是祖先的點的邊

##### forward edge

連向子樹節點的邊

### Tarjan

https://oi-wiki.org/graph/scc/


### Kosaraju

怎麼找到強連通分量呢？回憶之前提到 Tarjan 的算法是個萬能算法，的確，那個算法可以稍做修改就得到有向圖的版本。不過由於 Tarjan 的算法稍微比較複雜，因此在競賽上最常見的一個概念上比較簡單的 Kosaraju 演算法。Kosaraju 演算法與Tarjan 算法不同的是，與其著重在 DFS 樹上小孩與父親的關係，Kosaraju 演算法更直接的觀察到，如果我們好好的在圖上 DFS 的話，那麼每次走到的節點們就會各自形成強連通分量！最簡單的例子就是當圖是一個有向無環圖（directed acyclicgraph, DAG）時時，根據定義，每個節點自成一個強連通分量，那麼此時如果我們照著拓樸順序的反序進行 DFS 的話，那麼每次都只會搜集到恰一個節點（前面的人都被拜訪過了），那麼這樣求出的 SCC 就是正確的。

推廣在 DAG 上的版本，對於一般的有向圖上的節點 x 與 y ，如果 x 能到達 y 且 y 不能到達 x 的話，那麼 x 與 y 一定屬於不同的強連通分量，如果這時 x 比 y 早DFS 到的話，那就會誤把 y 與 x 放在同一個 SCC 裡。因此我們希望對於所有這樣的點對，y 都要在 x 之前被 DFS 拜訪到。要怎麼達到這個要求呢？Kosaraju 演算法的精髓就在於它建立有向圖 G 的反圖 G′ ，然後在 G′ 上進行 DFS 並記錄下所有節點離開的時間，接著將節點由離開時間大到小排列，則按照這個順序在原圖上DFS 就能正確地找出所有的 SCC 了。
我們來探討一下 Kosaraju 演算法的正確性，對於上述 x 可以走到 y 但 y 不能走到x 的點對，在 G′ 上會變成 y 可以走到 x 而 x 不能走到 y 。考慮在反圖上 DFS 到 y 時 x 的狀態：
• 如果 x 已經被拜訪過了：那顯然 x 的離開時間小於 y 的離開時間。
• x 還未被拜訪：那從 y 開始 DFS 會經過 x ，由於 y 要等 x 離開才能離開，因此 x 的離開時間依然小於 y 的離開時間。

既然可以保證 Kosaraju 演算法給出的序列符合我們的要求，那接續在原圖上 DFS找強連通分量的正確性也就被保證了。實作上也很簡單，只需要照著做兩次 DFS 即可，時間複雜度 O(|V | + |E|)

![](https://i.imgur.com/StiB3H9.png)



## 求SCC有什麼用

- 縮點
- 轉DAG

### 例題

https://cses.fi/problemset/task/1686

```cpp=
inline void solve() {
    int n,m;cin>>n>>m;
    V<int> v(n);
    for(auto& i:v)
        cin>>i;
    V<V<int>> e(n);
    for(int i=0;i<m;i++){
        int a,b;cin>>a>>b;
        e[a-1].emplace_back(b-1);
    }
    V<ll> val;
    V<bool> ins(n,false);
    V<int> dfn(n,-1),low(n),s,scc(n);
    F<void(int)> dfs=[&](int x){
        if(~dfn[x]) return;
        static int t=0; 
        dfn[x]=low[x]=t++;
        ins[x]=true,s.push_back(x);
        for(auto i:e[x])
            if(dfs(i),ins[i])
                low[x]=min(low[x],low[i]);
        if(dfn[x]==low[x]){
            static int cnt=0;
            val.push_back(0);
            int p; do{
                p=s.back();s.pop_back(),ins[p]=false;
                scc[p]=cnt,val[cnt]+=v[p];
            }while(p!=x); cnt++;
        }
    };
    for(int i=0;i<n;i++) dfs(i);
    V<V<int>> e2(val.size());
    for(int i=0;i<n;i++)
        for(auto j:e[i])
            if(scc[i]!=scc[j])
                e2[scc[j]].emplace_back(scc[i]);
    for(auto& i:e2){
        sort(i.begin(),i.end());
        i.resize(unique(i.begin(),i.end())-i.begin());
    }
    V<ll> dp(val);
    for(int i=0;i<(int)dp.size();i++)
        for(auto j:e2[i])
            dp[j]=max(dp[j],val[j]+dp[i]);
    cout<<*max_element(dp.begin(),dp.end())<<endl;
}
```