有向cycle検出・sink/source peeling
三色DFSのrecursion stackまたは入次数・出次数零の反復削除により有向cycleを検出し、必要ならcycleへ到達するcoreと処理可能なDAG部分を分離する。
この典型を扱う単元: 有向cycle検出・sink/source peeling
検索別名: Kahn elimination、sink peeling、three-color DFS、有向cycle検出、有向グラフの葉刈り
未知問からこの典型を見つける手掛かり
- 扱う対象
- cycle core
- directed graph
- source/sink
- 使う手掛かり
- cycleに残る頂点
- 出次数0を削除
- 有向cycleが一つでも存在
- 保つ不変量
- DFS recursion stack
- remaining indegree/outdegree
- 求めるもの
- cycle core
- cycle存在判定
- 削除順
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: グラフモデルと構造
関連する典型
- 単一サイクル成分とgraph core: 局所次数条件を満たさない頂点をqueueで除き、残存核の不変条件を読む発想が共通する。
学習成果と学習単位
三色DFSまたはKahn型peelingの不変条件を説明し、有向cycleの存在を判定して必要ならcycleへ残るcoreを抽出できる。
有向cycle検出・sink/source peelingで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。