ABC 315 E — Prerequisites

考察

本 i から前提 P_{i,j} へ有向辺を張ると、本1に必要な集合は頂点1から到達可能な頂点と一致する。全書籍を読める保証から依存関係には cycle がない。辺の向きは「本→先に読む前提」なので、そのままの DFS postorder なら前提を出力してから本へ戻り、必要集合内の読書順になる。「最小冊数」は選択最適化ではなく、推移的な全前提が必須なので到達可能集合として一意に決まる。一般の topological order との向きを混同せず、i→prerequisite の graph では DFS の finish order が読む順になる。

採用する候補: 頂点1から依存先へ DFS し、各頂点を帰りがけに記録する postorder を出力する。

到達可能集合だけを訪れ、全辺 i→p について p が i より先に記録されるので集合抽出と順序付けを同時に行える。

棄却する候補: 全 N 冊をトポロジカル sort し、その後で本1に必要かを別に判定する。

正解にはなるが不要な頂点まで処理・filter する二段構成で、依存先 DFS の postorder だけで十分である。

visited[1]=true から DFS/BFS で依存辺をたどる。DFS なら各子の探索後に v を answer へ push し、最後に根1だけを除いた列をそのまま出力する。再帰を避けるなら enter/exit を持つ明示 stack で postorder を作る。

典型の発動条件

依存 DAG の到達閉包

発動条件: ある対象を実行するために必要な前提すべてを最小集合として求めるとき。

対象から prerequisite 辺をたどった reachable set を採用する。

DFS postorder による依存順

発動条件: 辺がタスクからその前提へ向いている DAG で、前提を先に並べたいとき。

探索終了時に記録して各 prerequisite を利用側より前へ置く。

問題固有の要素

問題文が「必要集合は一意」と述べる理由は、前提のどれかを選ぶのではなく AND 条件で推移閉包全体が強制されるからである。

別の問題へ持ち帰る視点: 依存問題では edge が AND/OR のどちらかを判別すると、最小集合が探索だけか最適化かを切り分けられる。

正当性

1から前提辺を辿ると必要本だけを列挙する。DAGでのDFS postorderでは辺i→pのpが必ずiより先に記録され、既訪問も既に完了かDAG上の依存順に含まれる。根1を除けば必要本を各一回、前提を先に読む順に出力する。

実装上の注意

  • N=2×10^5 なので言語によっては再帰深度を回避する。共有前提を一度だけ出力し、頂点1自身は postorder から除く。

復習の核

  • 辺の向きを紙に一つ書き、preorder/postorder/reverse のどれが前提先行になるか確かめる。集合の最小性は到達頂点が全て必須であることから説明する。

計算量と制約

時間

本数N、前提辺M。必要部分だけDFSは O(N+M) の範囲。

空間

隣接、visited、明示stack、出力 O(N+M)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 2 \times 10^5; 0 \leq C_i < N; \sum_{i=1}^{N} C_i \leq 2 \times 10^5; C_1 \geq 1; 1 \leq P_{i,j} \leq N; P_{i,j} \neq P_{i,k} for 1 \leq j < k \leq C_i.; It is possible to read all the books.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Prerequisites の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: DAGのtopological processing

主題
  • DAGのtopological processing: 依存辺の向きを定め、入次数またはpostorderからtopological順を作って制約伝播・DP・scheduleを処理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: DAGのtopological processing

      執筆: abc-explanation-author1.1.1 / revision 2

      学習の位置

      体系上の位置: DAGのtopological processing

      • 依存辺の向きを定め、入次数またはpostorderからtopological順を作って制約伝播・DP・scheduleを処理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

      先に読む単元:

      • 状態グラフのモデリングと探索 — 暗黙状態と重みなし合法遷移を頂点・辺へ写し、探索目的・訪問条件・frontierに応じてBFS・DFS・backtrackingを選ぶ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題