強連結成分分解 (Kosaraju)
概要
有向グラフにおいて互いに到達可能な頂点は強連結であるといい， 全ての頂点を強連結なもの同士のグループに分けることを強連結成分分解 (SCC : Decomposition of Strongly Connected Components) という．概念についてはここがわかりやすい． 強連結成分を縮約したグラフは DAG になる．
やることはシンプルで， 2 回 DFS (深さ優先探索) するだけ． まず DFS の戻りがけ順，つまり DFS で最後に訪れたタイミングの早い方から順番に番号をつける．次に，番号の大きな頂点から辺の向きを逆にしたグラフで DFS を行う．少し考えると，1 度の DFS で到達可能な頂点は同じ強連結成分に含まれるということが言える． これとは別の Tarjan の方法 (tarjan-scc.cc) もある．
計算量
$O(E+V)$
使い方
cmp[v] = 頂点 v が含まれる連結成分の番号 となるような vector<int> cmp を返す．トポロジカル順序の逆に振られる．
実装
std::vector<int> kosaraju(const Graph &g) {
int n = g.size(), sz = 0;
Graph rg(n);
std::vector<int> stk, cmp(n, -1), added(n), visited(n), ord(n);
for (auto &es : g) {
for (auto e : es) {
std::swap(e.src, e.dst);
rg[e.src].emplace_back(e);
}
sz += es.size();
}
stk.resize(n + sz);
sz = 0;
for (int i = 0; i < n; i++) {
if (visited[i]) continue;
int s = 0;
stk[s++] = i;
while (s != 0) {
int v = stk[s - 1];
visited[v] = true;
bool pushed = false;
for (auto &e : g[v]) {
int dst = e.dst;
if (!visited[dst]) {
stk[s++] = dst;
pushed = true;
}
}
if (pushed) continue;
int t = stk[s - 1];
if (!added[t]) {
added[t] = true;
ord[n - ++sz] = t;
}
--s;
}
}
int k = 0;
for (int &u : ord) {
if (cmp[u] != -1) continue;
int s = 0;
stk[s++] = u;
while (s != 0) {
int v = stk[--s];
cmp[v] = k;
for (auto &e : rg[v]) {
int d = e.dst;
if (cmp[d] == -1) stk[s++] = d;
}
}
++k;
}
return cmp;
}