強連結成分分解のお勉強

Programming

Spaghetti Sourceにワンパスでできるプログラムがあったので読んだ。
http://www.prefield.com/algorithm/graph/strongly_connected_components.html

  • グローバル変数
    • num[]…訪問順(time)
    • low[]…代表元リンク
    • S、inS…成分未確定頂点のスタック(inSはスタックに入ってるかどうかのフラグ)
  • 探索は深さ優先探索で、各頂点の訪問は1回ずつ。
    • つまり、探索木を考えることができる。
    • 探索木の特徴:ある強連結成分に属する頂点は、全てある頂点の配下にあり、その頂点とは、成分の中で最初に訪問したものである。
  • 上記の特徴をもつ頂点を、ここでは代表点と呼ぶことにする。
  • 点Aが代表点かどうかは、その頂点の訪問が終了した時点で確定できる。
    • 具体的な方法
    • 配下の頂点から出ている、訪問済み頂点へのリンクを検査する。
    • Aより訪問順の若い頂点Bへのリンクがあり、
    • かつ、そのリンク先Bが未確定の頂点である場合
    • →未確定 == Aへのリンクをもつ、 なので、
    • →AとBは同じ強連結成分に属すことになる。つまりAは代表点ではない。
    • 逆も真。
  • 上記の判定を行うのが未確定の頂点を保管するスタックS(正確にはinSを用いる)
    • inSが真であるような訪問済み頂点のうち最も若いものを計算することで実現する
    • この計算は再帰的に再利用できる
  • 代表点であることが確定した時点で、スタックに残っている代表点以降の点は全て同じ強連結成分に属しているので、これらをまとめてやればよい。
  • ちなみに、DFSを利用している性質上、おそらくトポロジカルソートの機能がおまけとして付いてくる。強連結成分分解とトポロジカルソートには深い関係があるので、こちらもセットで使うとお得かもしれない。