グラフの連結成分の発見

連結成分

連結成分は、セット内のすべての頂点が何らかのパスを通じて他のすべての頂点に到達できる頂点の最大セットです。

無向グラフ

無向グラフでの連結成分の発見は簡単です：

1. 未訪問のノードからDFS/BFSを開始
2. 到達したすべてのノードが同じ成分に属する
3. 次の未訪問ノードから繰り返す
4. すべてのノードが訪問されるまで続ける

有向グラフ：強連結成分（SCC）

有向グラフでは、強連結成分はすべてのノードが辺の方向に従って他のすべてのノードに到達できる最大セットです。

Kosarajuのアルゴリズム:

1. DFSを実行し終了時刻を記録
2. グラフを転置（すべての辺を逆転）
3. 転置グラフで終了時刻の逆順にDFSを実行
4. ステップ3の各DFS木がSCC

時間計算量

すべての成分発見アルゴリズムは**O(V + E)**で実行されます。