強連結成分分解 (Tarjan)
概要
**注意** バグってるので使ってはいけない 代わりに graph/kosaraju.cc を使うこと強連結成分分解を行う Tarjan のアルゴリズムです． 同じことができるアルゴリズムに，蟻本のおかげでよく知られるようになった(?) Kosaraju の方法 (graph/kosaraju.cc) もあります． どっちもかなり頭が良いですがこっちの方が早く発表されたそうです．Spaghetti Source もこっちです．
$ord(v)$ を $v$ の DFS 順序 (DFS で $v$ に最初に訪れた順番で振った番号)， $low(v)$ を $v$ の lowlink ($v$ から DFS 木に含まれる辺を任意の回数，含まれない辺を一度だけ使って訪れることができる頂点の $ord$ の最小値) とします．
最初に空のスタックを用意し，グラフの適当な頂点から DFS をします. その際, DFS の入りがけのタイミングで頂点をスタックに追加していきます． SCC (強連結成分) は DFS 木上で部分木になるという性質があり，SCC の根を $r$ とすると，SCC の中で $r$ だけが $ord( r ) = low( r )$ を満たします． この性質を使って根 $r$ を発見できます． さらに DFS で $r$ から抜けがけのタイミングでは，$r$ と同じ SCC の頂点は，全てスタック中で $r$ の上に積まれています． したがって，$r$ がスタックから取り出されるまに取り出される頂点が一つの SCC をなすことになります. DFS 木の葉のほうから順に SCC をまとめていけば，全ての強連結成分が見つけられます． これを全ての連結成分で繰り返します．
下の実装は Wikipedia の擬似コードを C++ にしただけです．非再帰にはできなかったのでコンテストでは kosaraju.cc を使ったほうがいいです．
計算量
$O(E + V)$
使い方
cmp[v] = 頂点 v が含まれる連結成分の番号 となるような vector<int> cmp を返す．トポロジカル順序の逆に振られる．
実装
std::vector<int> tarjan(const Graph &g) {
int n = g.size(), idx = 0, k = 0, s = 0;
std::vector<int> ord(n, -1), low(n), onS(n), cmp(n), stk(n);
static const std::function<void(int)> dfs = [&](int v) {
ord[v] = low[v] = idx++;
stk[s++] = v;
onS[v] = true;
for (auto &e : g[v]) {
int w = e.dst;
if (ord[w] == -1) {
dfs(w);
low[v] = std::min(low[v], low[w]);
} else if (onS[w]) {
low[v] = std::min(low[v], ord[w]);
}
}
if (low[v] == ord[v]) {
while (1) {
int w = stk[--s];
onS[w] = false;
cmp[w] = k;
if (w != v) break;
}
++k;
}
};
for (int v = 0; v < n; v++)
if (ord[v] == -1) dfs(v);
return cmp;
};