概要

DAG（有向非巡回グラフ）上で、前提関係を満たしながら「番号が最も小さい科目」を優先的に選ぶトポロジカルソートを行う問題です。

考察

問題の本質

科目の前提関係は「科目 \(A\) を先に履修しないと科目 \(B\) を履修できない」という有向辺 \(A \to B\) で表現できます。これはまさに 有向非巡回グラフ（DAG） の構造であり、すべての科目を前提関係に矛盾なく並べることは トポロジカルソート に対応します。

普通のトポロジカルソートとの違い

一般的なトポロジカルソートでは、有効な順序が複数存在しうります。しかし本問では「履修可能な科目の中から 番号が最も小さいもの を選ぶ」という追加条件があります。

例えば、\(N=3\)、前提関係なしの場合、トポロジカルソートとしては \((1,2,3)\), \((2,1,3)\), \((3,2,1)\) など多数ありますが、本問のルールでは常に番号最小の科目を選ぶので、答えは \((1, 2, 3)\) の一通りに定まります。

素朴なアプローチの問題点

毎ステップで「履修可能な科目」を全探索して最小番号を見つけると、\(1\) ステップあたり \(O(N)\)、全体で \(O(N^2)\) となり、\(N = 2 \times 10^5\) では TLE の恐れがあります。

解決方法

履修可能な科目の集合を 最小ヒープ（優先度付きキュー） で管理すれば、最小番号の取り出しが \(O(\log N)\) で行えます。

アルゴリズム

以下は 優先度付きキューを用いたトポロジカルソート（辞書順最小）の手順です。

1. 入次数の計算: 各科目について、前提科目の数（＝入次数 \(\text{in\_degree}[v]\)）を求める。
2. 初期化: 入次数が \(0\) の科目（前提がない科目）をすべて最小ヒープに追加する。
3. 繰り返し処理:
   • ヒープから最小の番号の科目 \(u\) を取り出し、履修順に記録する。
   • \(u\) から辺が出ている科目 \(v\) すべてについて、\(\text{in\_degree}[v]\) を \(1\) 減らす。
   • \(\text{in\_degree}[v]\) が \(0\) になったら、\(v\) をヒープに追加する。
4. ヒープが空になるまで繰り返す。

具体例: \(N=4\), 前提関係: \(1 \to 3\), \(2 \to 3\), \(3 \to 4\)

• 初期: 入次数 \(0\) は科目 \(1, 2\) → ヒープ: \(\{1, 2\}\)
• \(1\) を取り出し → 科目 \(3\) の入次数が \(2 \to 1\) → ヒープ: \(\{2\}\)
• \(2\) を取り出し → 科目 \(3\) の入次数が \(1 \to 0\) → ヒープ: \(\{3\}\)
• \(3\) を取り出し → 科目 \(4\) の入次数が \(1 \to 0\) → ヒープ: \(\{4\}\)
• \(4\) を取り出し → 完了。答え: \(1\ 2\ 3\ 4\)

計算量

• 時間計算量: \(O((N + M) \log N)\)
  • 各科目は最大 \(1\) 回ヒープに追加・削除され、各操作に \(O(\log N)\)。辺の処理は合計 \(O(M)\)。
• 空間計算量: \(O(N + M)\)
  • 隣接リストに \(O(N + M)\)、ヒープに最大 \(O(N)\)。

実装のポイント

• 最小ヒープの利用: Python の heapq はデフォルトで最小ヒープなので、そのまま使うだけで番号最小の科目を優先的に取り出せます。

• 高速入力: \(N, M\) が最大 \(2 \times 10^5\) のため、sys.stdin.buffer.read() で一括読み込みして高速化しています。

• 1-indexed の配列: 科目番号が \(1\) から始まるので、配列サイズを \(N+1\) にして添字をそのまま使えるようにしています。

  ソースコード

import heapq
import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    in_degree = [0] * (N + 1)
    adj = [[] for _ in range(N + 1)]
    
    for _ in range(M):
        a = int(input_data[idx]); idx += 1
        b = int(input_data[idx]); idx += 1
        adj[a].append(b)
        in_degree[b] += 1
    
    heap = []
    for i in range(1, N + 1):
        if in_degree[i] == 0:
            heapq.heappush(heap, i)
    
    result = []
    while heap:
        u = heapq.heappop(heap)
        result.append(u)
        for v in adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                heapq.heappush(heap, v)
    
    print(' '.join(map(str, result)))

main()

---

この解説は claude4.6opus-thinking によって生成されました。