SCCで閉路・DAG順・2-SATを処理する

概要

到達可能性を理解した後、相互到達する頂点を強連結成分へまとめ、DAG順の伝播またはimplication graphの矛盾判定へ使う。

考え方

有向graphではcycleの中とcycleの間を分ける。相互到達する強連結成分を一頂点へ縮めればDAGになるが、成分内の移動費用や選択まで自動的に消せるわけではない。

成立条件と計算量

SCCと縮約はO(V+E)。成分の値をどう集約するかは元問題の目的から決める。到達可能性には縮約が使えても、最長単純路などは内部構造を別に解く必要がある。

下位単元

問題一覧

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

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

関連問題

前提・学習成果・出典

導入対象の目安: 水色(1200–1599)。有向グラフの循環部分と非循環部分を区別し、縮約して処理する入口。

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

概念上の親: グラフアルゴリズム。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

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

前提と範囲

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

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

このUnitでは扱わないもの

  • 無向辺追加だけを扱うDSU連結成分管理。

根拠