強連結成分分解

有向グラフ上の部分集合Sの任意の頂点u, vについて，uからvに到達可能であるときSは強連結である。Sにどの頂点を加えても強連結にできないとき，Sは強連結成分である。

有向グラフGについて全ての強連結成分をつぶして一つにすると、グラフはDAGになる。

編集中