強連結成分（SCC）とは

強連結成分（SCC, Strongly Connected Component） = 有向グラフにおいて、互いに行き来が可能な頂点の集合。

• SCC を求めることを 強連結成分分解 という
• 元の有向グラフが DAG でなくとも、そのグラフの SCC は DAG を形成する

強連結成分分解の方法

処理の流れ

1. 対象グラフ $G$ の探索：頂点ラベリング
   1. 適当に選んだ $G$ の未探索の頂点から深さ優先探索を行い、帰りがけ に頂点を番号ラベリングする
      • 番号は1つずつ増やしていく
   2. 未探索の頂点がなくなるまで繰り返す
      • 2回目以降の探索において、それ以前の探索で訪問済みの頂点は探索対象に含めない
2. $G$ の逆グラフ $G^T$ を作成
   • 1で $G$ に付与した番号ラベルを引き継ぐ
3. 逆グラフ $G^T$ の探索：SCC 分解
   1. 未探索のうち、番号ラベルが一番大きい頂点 からグラフ探索
   2. 探索した頂点の集合 = 1つの SCC
   3. 未探索の頂点がなくなるまで繰り返す

基本的な考え方（つまり何をやっているのか？）

説明の便宜上、SCC1 → SCC2 のパスが存在する場合、「SCC1 は SCC2 より上流にある」 と表現する。

• $G$ の頂点ラベリング
  • 目的：各頂点が属する SCC が他と比べて上流・下流どちらなのかの判断をつけること
  • 最大の番号ラベルを持つ頂点 = $G$ の最も上流の SCC に属する頂点
    • 頂点 A からスタートする1回の深さ優先探索を行うと、A と同じ or A より下流の SCC の頂点はすべて探索できる
    • 帰りがけ探索でラベリングするので、上流 SCC には下流 SCC のどの頂点よりも番号が大きい頂点が最低1つ存在する
    • 未探索の頂点 B が残っていた場合、頂点 B は A よりも上流の SCC に属する
    • 次に頂点 B からスタートする深さ優先探索を行うと、探索された頂点全てに A より大きな番号が割り当てられる
• 逆グラフ $G^T$ の探索
  • 最大の番号ラベルを持つ頂点 = $G^T$ の最も下流の SCC に属する頂点
    • 逆グラフなので、$G$ とは上流・下流関係が逆転
  • 最下流の頂点から探索をスタートするので、たどり着ける頂点は同じ SCC に属するものだけ
    • つまり、1回の探索でたどった頂点は全てを同じ SCC のもの
  • よって「未探索のうち、最大ラベルのものから探索スタート」を繰り返せば、1回の探索につき1つ SCC が求められる

【NOTE】トポロジカルソート

この手法では、SCC は $G^T$ において下流（$G$ において上流）のものから順に求まる
→ 順にリストに格納していけば、トポロジカルソート済みの SCC リストが得られる

具体例

例題として、以下の有向グラフ $G$ における SCC を求める。

適当に選んだ頂点から深さ優先（帰りがけ探索）し、1から番号を増やしながらラベリング：

まだラベルのない頂点があるので、その中から適当に頂点を選び、そこから同様に深さ優先探索（帰りがけ探索）：

$G$ のエッジをすべて逆向きにしたグラフ $G^T$ を用意：

頂点のうち、ラベル番号が最大のものを選んでグラフ探索 → 通った頂点はすべて1つの SCC に属する：

未探索の頂点のうち、ラベル番号が最大のものを選んでグラフ探索 → 通った頂点はすべて1つの SCC に属する：

未探索の頂点のうち、ラベル番号が最大のものを選んでグラフ探索 → 通った頂点はすべて1つの SCC に属する：

すべての頂点を探索し、SCC が全て求まった：