概要

この問題は、ある科目の履修には他の科目を事前に履修している必要があるという条件のもとで、すべての科目を履修する順序を求めるものです。ただし、履修可能な科目の中では番号が最も小さいものを優先します。

考察

この問題は典型的な「トポロジカルソート」によって解くことができます。
各科目をノードと見なし、「科目 \(A\) を履修しないと科目 \(B\) は履修できない」という関係を有向エッジ \(A \rightarrow B\) と考えると、すべての科目を前提関係に従って並べ替える必要があり、これはまさにトポロジカルソートの応用そのものです。

さらに、普通のトポロジカルソートではなく、「選べる候補の中では最も番号が小さい科目を選ぶ」という制約があります。
たとえば、入次数が \(0\) のノードが複数ある場合、それらのうち最も番号が小さいものを選びたいので、優先度付きキュー（ヒープ） を使うことで効率的に実現できます。

素朴な方法（毎回リストを走査して最小の入次数0のノードを探す）では、最悪の場合 \(O(N^2)\) となり、制約 \(N \leq 2 \times 10^5\) では間に合いません。
そこで、ヒープを使うことで最小値取得を高速に行い、全体を効率よく処理します。

アルゴリズム

この問題では 入次数に基づくトポロジカルソート（Kahnのアルゴリズム） を使います。具体的には以下の手順で進めます：

1. 各ノードの入次数（その科目の前提となる科目の数）を管理する配列 in_degree を準備。
2. グラフを隣接リスト形式で構築：科目 \(A_j \rightarrow B_j\) のような依存関係を記録。
3. 最初に、入次数が \(0\) のノード（前提がない科目）をすべて 優先度付きキュー（ヒープ） に追加。
4. キューが空になるまで以下を繰り返す：
   • キューから最も番号が小さいノードを取り出す（これが次の履修科目）。
   • 取り出したノードから伸びる辺を削除（つまり、そのノードを履修したことにする）。
   • 辺の先のノードの入次数を \(1\) 減らし、それが \(0\) になったらキューに追加。
5. 取り出した順が答えとなる。

このように、ヒープを使うことで「入次数が \(0\) の中で最も番号が小さいノード」を効率的に取り出すことができます。

例

例えば、科目が3つあり、 - 科目1 → 科目2 - 科目1 → 科目3

という前提があるとき、科目1を最初に履修し、その後科目2と科目3のうち番号が小さい方（科目2）を次に履修します。最終的な順序は [1, 2, 3] になります。

計算量

• 時間計算量: \(O((N + M) \log N)\)
  • 各ノードをヒープに追加・取り出しする操作が \(N\) 回、それぞれ \(O(\log N)\)。
  • 各エッジを1回だけ処理するので、辺の処理に \(O(M)\)。
• 空間計算量: \(O(N + M)\)
  • グラフの隣接リストと入次数配列に \(O(N + M)\) 必要。

実装のポイント

• 入力が多いので sys.stdin.read を使って高速化している。

• ヒープはPythonの heapq を使用し、自動的に最小値が先頭に来るようにしている。

• グラフ構築時に、隣接リストと入次数を同時に更新することを忘れない。

• 結果の出力は ' '.join(map(str, result)) で行うと高速かつ簡潔。

  ソースコード

import heapq
import sys
from collections import defaultdict, deque

input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    
    graph = defaultdict(list)
    in_degree = [0] * (N + 1)
    
    idx = 2
    for _ in range(M):
        a = int(data[idx])
        b = int(data[idx+1])
        graph[a].append(b)
        in_degree[b] += 1
        idx += 2
    
    # 初期化：入次数が0の頂点を優先度付きキューに入れる
    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 graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                heapq.heappush(heap, v)
    
    print(' '.join(map(str, result)))

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。