競プロノート

Appearance

SCC（強連結成分分解） ​

有向グラフを、互いに到達可能な頂点の集合（強連結成分）に分解するアルゴリズム。

特徴 ​

項目内容
用途強連結成分分解・閉路の解析・DAGへの縮約
計算量O(V+E)
空間計算量O(V+E)

考え方 ​

Kosaraju法を使用する。

  1. 元のグラフでDFSし、帰りがけ順を記録する。
  2. 全辺を反転したグラフを作る。
  3. 帰りがけ順の逆順で、反転グラフに対してDFSする。
  4. 各DFSで訪れた頂点が1つの強連結成分になる。

実装 ​

cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n), rg(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        rg[b].push_back(a);
    }

    // 1回目：帰りがけ順を取得
    vector<bool> visited(n);
    vector<int> order;
    auto dfs = [&](auto&& self, int v) -> void {
        visited[v] = true;
        for (int nv : g[v]) if (!visited[nv]) self(self, nv);
        order.push_back(v);
    };
    for (int v = 0; v < n; v++) if (!visited[v]) dfs(dfs, v);

    // 2回目：逆向きのグラフで成分分解
    vector<int> comp(n, -1);
    vector<vector<int>> groups;
    auto rdfs = [&](auto&& self, int v, int id) -> void {
        comp[v] = id;
        groups[id].push_back(v);
        for (int nv : rg[v]) if (comp[nv] == -1) self(self, nv, id);
    };
    reverse(order.begin(), order.end());
    for (int v : order) {
        if (comp[v] != -1) continue;
        groups.emplace_back();
        rdfs(rdfs, v, (int)groups.size() - 1);
    }

    cout << groups.size() << '\n';
    for (const auto& group : groups) {
        cout << group.size();
        for (int v : group) cout << ' ' << v;
        cout << '\n';
    }
}

使用例 ​

入力（0-indexed、有向グラフ）

text
6 7
0 1
1 2
2 0
2 3
3 4
4 3
4 5

出力

text
3
3 0 2 1
2 3 4
1 5

3つの強連結成分に分解される。

  • {0, 1, 2}
  • {3, 4}
  • {5}

成分IDの利用 ​

cpp
// uとvが同じ強連結成分か
if (comp[u] == comp[v]) {
    // 互いに到達可能
}

// 強連結成分の個数
int k = groups.size();

SCCをDAGに縮約する ​

各強連結成分を1頂点にまとめると、DAGになる。

cpp
int k = groups.size();
vector<vector<int>> dag(k);
for (int v = 0; v < n; v++) {
    for (int nv : g[v]) {
        if (comp[v] == comp[nv]) continue;
        dag[comp[v]].push_back(comp[nv]);
    }
}
for (auto& vs : dag) {
    sort(vs.begin(), vs.end());
    vs.erase(unique(vs.begin(), vs.end()), vs.end());
}

この実装では成分IDがトポロジカル順になっているため、 異なる成分間の辺 u → v に対して comp[u] < comp[v] が成立する。

縮約後のDAGに対してDPなどを適用できる。

注意点 ​

  • 強連結成分は有向グラフに対する概念。
  • 単なる到達可能性と異なり、双方向に到達できる必要がある。
  • 2回目のDFSは元のグラフではなく、逆向きのグラフで行う。
  • 1回目のDFSでは帰りがけ順を記録する。
  • 強連結成分を縮約すると必ずDAGになる。
  • 再帰DFSは頂点数が大きい場合、スタックオーバーフローに注意。
  • SCCが1頂点だけの場合、それだけでは自己ループの有無は分からない。

関連 ​