強連結成分分解
強連結とは、有向グラフ$G$の部分集合$S$の任意の２頂点を選んだとき、頂点同士が互いに行き来可能であることである。
部分集合$S$にほかの頂点集合を付け加えても強連結にならないとき、部分集合$S$は強連結成分(SCC, Storongly Connected Component)である。
有向グラフを強連結成分となる部分集合ごとに分解することを強連結成分分解と呼ぶ。
強連結成分部分を頂点とみなすと非DAGをDAG(有向非巡回グラフ)とみなして走査できるようになる。
実装
有向グラフ$G$をDFSで探索し帰りがけに頂点を番号でラベリングする。これを未探索の頂点がなくなるまで繰り返す。
辺の方向を逆向きにした$G^T$を一番大きい番号の頂点から探索する。探索が完了した頂点の集合が1つのSCCとなる。
未探索の頂点がなくなるまで探索することですべてのSCCをみつけることができる。
２回目のグラフ探索が逆グラフを探索するのは、最大番号の頂点は逆グラフだと最下流になるため、元のグラフにおける下流の連結成分まで誤って連結成分として探索してしまうことがなくなる。
計算量は頂点と辺に線形で $O(|E|+|V|)$。