SCCで閉路・DAG順・2-SATを処理する
概要
到達可能性を理解した後、相互到達する頂点を強連結成分へまとめ、DAG順の伝播またはimplication graphの矛盾判定へ使う。
考え方
有向graphではcycleの中とcycleの間を分ける。相互到達する強連結成分を一頂点へ縮めればDAGになるが、成分内の移動費用や選択まで自動的に消せるわけではない。
成立条件と計算量
SCCと縮約はO(V+E)。成分の値をどう集約するかは元問題の目的から決める。到達可能性には縮約が使えても、最長単純路などは内部構造を別に解く必要がある。
下位単元
- DAGのtopological processing — 緑色
- 有向cycle検出・sink/source peeling — 水色
- SCC・縮約DAG・トポロジカル順序 — 水色
- 2-SAT・含意グラフ — 青色
問題一覧
この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC214 H「Collecting」 公式問題
技能・出典
主題: 最小費用流・circulation(流量と費用を持つ残余networkを設計し、potential付き最短路・slope・cycle cancelingで流量別最小費用を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。追加で学ぶ技能: SCC・縮約DAG・トポロジカル順序(有向グラフの閉路を扱い、必要なら強連結成分へ縮約してDAG順に情報を伝播できる。)。 - ABC224 E「Integers on Grid」 公式問題
技能・出典
主題: DP遷移を因数分解・集約して加速する(遷移式を属性別極値・少数の重み付き和へ分解し、その集計値が更新について閉じることを示せる。)。既習技能: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / DAGのtopological processing(依存辺の向きを定め、入次数またはpostorderからtopological順を作って制約伝播・DP・scheduleを処理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。 dp_i=1+max_{a_j>a_i,同じ行または列}dp_j型の遷移を行別・列別最大へ圧縮する。遷移先がなければ0。同値のbatchでは全取得を済ませてから更新し、狭義不等号を保つ。sort後の集約はO(N)。主タグ: DP遷移の集約・高速化 / 補助タグ: DAGのtopological processing、event・値順のオフライン走査
- ABC304 Ex「Constrained Topological Sort」 公式問題主題: 交換論から選択順を導く
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: DAGのtopological processing(依存辺の向きを定め、入次数またはpostorderからtopological順を作って制約伝播・DP・scheduleを処理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 貪欲法と交換論 / 補助タグ: DAGのtopological processing
- ABC306 Ex「Balance Scale」 公式問題
技能・出典
主題: 包除・Möbius反転で重複を補正する(条件集合の重なり構造を特定し、包除またはMöbius反転の符号と範囲を正しく設定できる。)。既習技能: 部分集合・bitmask状態DP(bitmaskの各bitが表す意味を定め、部分集合間の遷移を正しく設計できる。) / DAGのtopological processing(依存辺の向きを定め、入次数またはpostorderからtopological順を作って制約伝播・DP・scheduleを処理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 集合上の包除原理 / 補助タグ: DAGのtopological processing、部分集合・bitmask状態DP
- ABC306 G「Return to 1」 公式問題
技能・出典
主題: 有向walkの周期・cycle差分gcd(往復可能な有向領域のclosed walk長が作る周期gcdを求め、巨大な指定歩数での到達可能性を判定できる。)。既習技能: SCC・縮約DAG・トポロジカル順序(有向グラフの閉路を扱い、必要なら強連結成分へ縮約してDAG順に情報を伝播できる。) / gcd不変量・差分構造(gcd不変量によって共通因子・差分・周期成分を分離し、rangeまたは剰余類ごとの問いを処理できる。)。主タグ: 有向walkの周期・cycle差分gcd / 補助タグ: gcd不変量・差分構造、SCC・縮約DAG・トポロジカル順序
- ABC324 F「Beautiful Path」 公式問題
技能・出典
主題: fractional programming・比率parametric search(比率候補xをbenefit-x·costの加法目的へ変換し、単調な判定問題を解いて最適比率を求められる。)。既習技能: DAGのtopological processing(依存辺の向きを定め、入次数またはpostorderからtopological順を作って制約伝播・DP・scheduleを処理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / 単調境界を証明して探索する(判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。)。主タグ: fractional programming・比率parametric search / 補助タグ: DAGのtopological processing、単調境界探索
- ABC335 E「Non-Decreasing Colorful Path」 公式問題主題: DSUによる連結成分管理・縮約
技能・出典
主題: DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。)。追加で学ぶ技能: DAGのtopological processing(依存辺の向きを定め、入次数またはpostorderからtopological順を作って制約伝播・DP・scheduleを処理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。 - ABC341 F「Breakdown」 公式問題主題: 資源・容量DP
技能・出典
主題: 資源・容量DP(資源軸の上限と更新順を選び、選択の重複を避けられる。)。既習技能: DAGのtopological processing(依存辺の向きを定め、入次数またはpostorderからtopological順を作って制約伝播・DP・scheduleを処理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 資源軸knapsack DP / 補助タグ: DAGのtopological processing
- ABC374 G「Only One Product Name」 公式問題
技能・出典
主題: 二部matching・Hall・Kőnig(左右の一対一割当をaugmenting pathまたは単位容量flowで解き、Hall条件・Kőnigの定理・path coverへ接続する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 推移閉包(各始点探索または中継許可集合の段階不変条件を保つWarshall更新で推移閉包を求め、必要なら初回到達段階も記録できる。) / SCC・縮約DAG・トポロジカル順序(有向グラフの閉路を扱い、必要なら強連結成分へ縮約してDAG順に情報を伝播できる。)。主タグ: 二部matching・Hall・Kőnig / 補助タグ: SCC・縮約DAG・トポロジカル順序、推移閉包
前提・学習成果・出典
導入対象の目安: 水色(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連結成分管理。