SCC・縮約DAG・トポロジカル順序

概要

強連結成分を一頂点へ縮約し、閉路を除いたDAG上の順序・DP・coverへ変換する。

考え方

強連結成分(SCC)は、互いに有向pathで到達できる頂点の極大集合である。頂点ごとに所属comp[v]を得たら、元の辺u→vでcomp[u]≠comp[v]のものを成分間辺へ写す。縮約に閉路があれば、閉路上の全成分が相互到達できて同じSCCになるはずなので矛盾する。したがって縮約はDAGである。

Kosarajuの二回のDFS

元graph Gと全辺を逆にしたG_revを用意する。G上で未訪問の全頂点からDFSし、各頂点を「全隣接先の探索後」にorderへ追加する。次に訪問をリセットし、orderの逆順で未訪問頂点を選び、G_rev上でDFSする。一回の探索で取れた頂点を一つのSCCにし、その全頂点へ同じcompを付ける。

Gの縮約辺A→Bがあれば、Aの最大DFS終了時刻はBの最大終了時刻より大きい。Aが先に探索されればBへ入って先に終了し、Bが先ならBからAへ戻れないのでB全体の終了後にAを探索するからである。従って未処理の最大終了時刻の成分Aは、元の縮約でsourceとなる。逆graphではAから別の未処理成分へ出られず、A内部には全頂点へ到達できるので、第二DFSがちょうどAを取り出す。これを繰り返すとsourceからsinkへの成分順になる。

成分リストから元頂点へ戻す

ライブラリを使う場合も、返された成分リストgroupsについて、各groups[c]の頂点vへcomp[v]=cを付ける。ACLのSCC仕様は、成分リストが元の辺に沿うトポロジカル順であることを保証する。成分内の頂点順には意味を持たせない。

成分値を初期化し、元辺から縮約辺を作り、source→sink順でDPを後続へ渡す。逆向きに後続の値を集約するなら逆順で走査する。到達可能性を保つ縮約でも、内部の単純path数や費用はcompだけでは復元できないため、元問題に必要な成分内情報を別に保存する。

成立条件と計算量

二回のDFSと逆辺の構築はO(V+E)時間・空間。縮約辺を重複のまま持つ構築もO(V+E)。成分対をsortして重複除去するならO(E log E)を加える。存在判定やmax DPでは重複を無視できても、辺の選び方を数える場合は元の多重辺と重複除去の意味を区別する。

問題一覧

この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 水色(1200–1599)。相互到達性で頂点をまとめ、縮約後がDAGになることを使う。

対象色の読み方は本書の読み方を参照してください。

概念上の親: SCCで閉路・DAG順・2-SATを処理する。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-scc-condensation

SCC・縮約DAG・トポロジカル順序

習得する技能

  • 有向グラフの閉路を扱い、必要なら強連結成分へ縮約してDAG順に情報を伝播できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: DAGのtopological processing。

このUnitを直接前提とする単元: 有向walkの周期・cycle差分gcd、2-SAT・含意グラフ。

DAGのtopological processingで得た考え方と実装を再利用し、SCC・縮約DAG・トポロジカル順序の発動条件・正当化・境界を重複なく学ぶ。

このUnitでは扱わないもの

  • SCC・縮約DAG・トポロジカル順序の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠