SCC・縮約DAG・トポロジカル順序
強連結成分を一頂点へ縮約し、閉路を除いたDAG上の順序・DP・coverへ変換する。
この典型を扱う単元: SCC・縮約DAG・トポロジカル順序
検索別名: SCC、condensation DAG、強連結成分分解
未知問からこの典型を見つける手掛かり
- 扱う対象
- DAG
- 強連結成分
- 有向graph
- 使う手掛かり
- 依存順
- 相互到達
- 閉路
- 保つ不変量
- DAG順
- 成分内同値
- 求めるもの
- 縮約
- 順序付け
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: グラフモデルと構造
関連する典型
学習成果と学習単位
有向グラフの閉路を扱い、必要なら強連結成分へ縮約してDAG順に情報を伝播できる。
SCC・縮約DAG・トポロジカル順序で学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC214 H「Collecting」 公式問題主題: 最小費用流・circulation / 主タグ
- ABC306 G「Return to 1」 公式問題主題: 有向walkの周期・cycle差分gcd / 補助タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。