強連結成分分解の実装と個人的なメモ

前提

有向グラフGの頂点の部分集合をSとする。

• Sが強連結であるとは、Sの任意の2頂点間が行き来可能であること
• Sが強連結成分であるとは、Sに他のどの頂点を追加してもそれ以上強連結にならないこと

強連結成分分解とは、強連結成分を1つの頂点にまとめること。こうしてまとめられた頂点でグラフを再構築すると、その有向グラフはDAGになる。

• グラフをDAGに再構築し、DAGに対してDPするのは典型
• 強連結成分分解を使って解くことができる有名問題として2-SATがある

強連結成分分解のアルゴリズムは単純で2回DFSを行うだけ。

1回目のDFSで各頂点に帰りがけの順を記録する。

2回目のDFSは元のグラフの辺を逆辺に置き換えたものに対して行う。1回目で採番した帰りがけの遅い順にDFSする。既に訪れた頂点を避けながらDFSすることで、その頂点から行き来できる頂点集合が1つの強連結成分となる。

2回のDFSで何をしているのか

これは参考に載せた、目指せグラフマスターのスライドP.11によくまとめられている。

1. 強連結な集合は辺を逆辺に置き換えても強連結のまま
2. DFSの帰りがけ順が遅い => 完成したDAGのトポロジカル順序において早い
3. 逆辺のDFSなら今見ている頂点から（2のトポロジカル順序における）後の強連結成分を訪れない

3が重要で、このトポロジカル順序を無視して逆辺のグラフにDFSすると、ある連結成分から、自身よりトポロジカル順序が前の連結成分へ移動してしまう可能性があり、本来連結成分ではない集合を連結成分としてしまう可能性がある。

実装

struct StronglyConnectedComponents {
  int n;
  vector<vector<int>> G, rG;
  vector<int> order, component;
  vector<bool> used;
  void dfs(int v) {
    used[v] = 1;
    for (auto nv : G[v]) {
      if (!used[nv]) dfs(nv);
    }
    order.push_back(v);
  }
  void rdfs(int v, int k) {
    component[v] = k;
    for (auto nv : rG[v]) {
      if (component[nv] < 0) rdfs(nv, k);
    }
  }

  StronglyConnectedComponents(vector<vector<int>> &_G) {
    n = _G.size();
    G = _G;
    rG.resize(n);
    component.assign(n, -1);
    used.resize(n);
    for (int v = 0; v < n; v++) {
      for (auto nv : G[v]) rG[nv].push_back(v);
    }
    for (int v = 0; v < n; v++) if (!used[v]) dfs(v);
    int k = 0;
    reverse(order.begin(), order.end());
    for (auto v : order) if (component[v] == -1) rdfs(v, k), k++;
  }

  /// 頂点(u, v)が同じ強連結成分に含まれるか
  bool is_same(int u, int v) { return component[u] == component[v]; }

  /// 強連結成分を1つのノードに潰したグラフを再構築する
  vector<vector<int>> rebuild() {
    int N = *max_element(component.begin(), component.end()) + 1;
    vector<vector<int>> rebuildedG(N);
    set<pair<int, int>> connected;
    for (int v = 0; v < N; v++) {
      for (auto nv : G[v]) {
        if (component[v] != component[nv] and !connected.count(pair(v, nv))) {
          connected.insert(pair(v, nv));
          rebuildedG[component[v]].push_back(component[nv]);
        }
      }
    }
    return rebuildedG;
  }
};

検証用問題

onlinejudge.u-aizu.ac.jp

参考

p.82から強連結成分分解の解説

https://hcpc-hokudai.github.io/archive/graph_scc_001.pdf

目指せグラフマスター from HCPC: 北海道大学競技プログラミングサークル

www.slideshare.net