競プロ用ライブラリを作る Advent Calendar 2024の20日目です.
SCCって?
有向グラフに関するアルゴリズムです. 日本語では「強連結成分分解」です.
まず, 「強連結成分」を次のように定義します.
- 二つの頂点$u$, $v$について, $u$から$v$へのパスと$v$から$u$へのパスが存在するとき, かつそのときに限り$u$と$v$は同じ強連結成分に属する
数学的な書き方をするなら「頂点全体を"両方向のパスが存在する"という同値関係で割った同値類」ですね.
一応同値関係の性質を満たしていることを軽く示しておきます.
- 自明なパスを考えると任意の頂点$v$で$v\sim v$なので, 反射律が成り立ちます
- $u\sim v$が成り立つなら2つのパスが入れ替えて$v\sim u$を示せるので, 対称律が成り立ちます
- $u\sim v$と$v\sim w$が成り立つならパスをくっつけて$v\sim w$を示せるので, 推移律が成り立ちます
こういう感じのグループ分けをするのがSCCです. これを線形時間でやるアルゴリズムがあります.
仕組み
とりあえず, まずは「指定された頂点の属する強連結成分」を計算する方法を見ます.
- その頂点から深さ優先探索で到達できる頂点を調べる
- 辺の向きを逆にしたグラフで同様に深さ優先探索する
- 1と2でどちらも到達できる頂点が同じ強連結成分に属している
1では「指定された頂点から到達できる頂点」を, 2では「指定された頂点に到達できる頂点」を調べます. どちらの条件も満たすときに同じ強連結成分に属するので, これで目的は達成できます.
これを全部の頂点を強連結成分に分けられるまでやればとりあえず目的は達成できますが, 各探索で最悪$O(N)$で, 連結成分の個数が最大$N$個なので合わせて最悪$O\left(N^2\right)$です.
これをベースに高速化していきます. まず, 2で全範囲の頂点を探索していたのを「1で到達できた頂点だけ」に絞って探索します. これで2では各連結成分の要素しか見なくなったので, 2での計算量は合計でも$O(N)$になりました.
細かい話
この高速化を行うには「同じ強連結成分の要素同士のパスは, その強連結成分に属している頂点だけで構成される」ということを示す必要があるので, 示します.
同じ強連結成分に属している2頂点$v, u$について, $v$から別の強連結成分に含まれる頂点$w$を通って$u$に向かうパスが存在したとします.
すると, 同じ強連結成分に属しているので$u\to v$のパスが存在し, また$v\to w\to u$のパスの一部分として$v\to w$, $w\to u$のパスが存在しているので, $v\to w$のパスと, $w\to v$のパス($w\to u$と$u\to v$をくっつけます)が存在します. 強連結成分の定義から, $w$は$v$や$u$と同じ強連結成分に属していると分かりますが, これは$w$が$u$や$v$と別の強連結成分に属しているという仮定と矛盾します.
ということで別の強連結成分の頂点を通過するパスは存在しないと示せました.
1の計算量も削ります. 1で行った探索を他の強連結成分でも使いまわすことを考えます.
さて, 強連結成分ごとに1つの頂点にまとめて新しいグラフを作ると, これはDAG(有向非巡回グラフ)になります. DAGとはループがない有向グラフのことです.
DAGの特徴ですが, グラフを深さ優先探索して帰りがけ順に頂点を並べると, 前に来た頂点から後ろに来た頂点へのパスは存在しません.
ちゃんと示す
頂点$u$, $v$を適当に選んで, $u$が前, $v$が後に来たとします.
$v\to u$のパスが存在するなら, DAGにループが存在しないことから$u\to v$のパスは存在できません (存在したら$v\to u$のパスとくっつけてループにできます)
$v\to u$のパスが存在しないなら, 探索木上では子孫関係にないことが分かります. そして$u$と$v$の最近共通祖先を見ると, $u$の枝より$v$の枝の方が後に探索されているはずです. $u$の枝より前に$v$には訪れていないので, DFSの性質から$u\to v$のパスが存在するなら$u$の子に頂点$v$も含まれるはずですが, これは「子孫関係にない」ということと矛盾します. よって, $u\to v$のパスは存在しません.
実装
頑張りましょう. 気分でイテレータを返すようにしてみました.
まとめ
いかがでしたか?
明日は定数倍が軽い対数時間を実装します.