片道の到達では同じ成分にならない
有向グラフでuからvへもvからuへも道があるとき、二つの頂点は同じ強連結成分に属します。道の長さ0も認めるので各頂点は自分自身へ到達でき、孤立した頂点も一つの成分です。辺の向きを無視した連結成分とは異なり、片方向につながっているだけでは一つにまとめません。相互到達可能性は同値関係になるため、頂点集合を重複のない成分へ分けられます。成分の中のすべての頂点対に直接の辺が必要なわけではなく、複数の辺を通る道があれば十分です。
三つの成分を縮約する
辺A→B、B→A、B→C、C→D、D→C、D→Eがあると、成分は{A,B}、{C,D}、{E}です。それぞれを一頂点へ縮めると、最初の成分から二番目、二番目から三番目への辺だけが残ります。この縮約グラフに有向閉路があれば、その閉路上の成分は互いに到達でき、別成分とした定義に反します。したがって縮約グラフはDAGです。元のグラフに閉路があっても、成分単位では依存関係をトポロジカル順で考えられます。
二回の探索で境界を見つける
Kosaraju型の方法は、向きを逆にしたグラフでDFSの終了順を求め、その逆順で元のグラフをDFSします。まだ成分番号が付いていない頂点からの一回の探索で、同じ強連結成分をまとめます。逆向きで終了順を取るという約束と、元のグラフを処理する順番は一組です。単なる頂点番号順やDFS開始順に置き換えると、外の成分へ越えてまとめてしまうことがあります。対称な別の説明では元と逆グラフの役割を交換するため、二つの版を途中で混ぜないようにします。
何を出力し何を数えるか
隣接リストでは二回のDFSと逆グラフの構築を合わせて時間O(V+E)です。逆向きの辺を別に保持するならその領域もO(V+E)、訪問済み印や成分番号はO(V)です。深いグラフでは再帰スタックの上限にも注意し、必要なら明示的スタックを使います。返す成分番号は実装によって変わり、番号そのものに大小の意味があるとは限りません。テストでは番号の一致ではなく、互いに到達可能な頂点が同じ集合になっているか、縮約が非巡回かを確かめます。