概要

前提科目の関係を有向グラフとみなし、「履修可能な科目のうち番号が最小のものを選ぶ」というルールに従った一意な履修順を求める問題です。

考察

各前提関係「\(A \rightarrow B\)（\(B\) の前に \(A\) が必要）」は、有向辺 \(A \to B\) として扱えます。すると「前提がすべて終わった科目」とは、入次数（未消化の前提の数）が \(0\) の頂点に対応します。

素朴に「毎回、全科目を走査して履修可能なものを探し、その中の最小番号を選ぶ」をすると、各ステップで \(O(N)\) 探索が必要になり、全体で \(O(N^2)\) となって \(N \le 2 \times 10^5\) では間に合いません。

そこで、 - 各科目について「未消化の前提数（入次数）」を管理しておき、 - 入次数が \(0\) になった科目をすぐ取り出せるようにデータ構造に入れる ことで高速化します。

さらに本問題は「履修可能な中で最小番号」を選ぶ必要があるため、入次数 \(0\) の集合は 最小値を取り出せる priority queue（最小ヒープ） で管理するのが自然です。

アルゴリズム

これは トポロジカルソート（Kahn 法） に「常に最小番号を選ぶ」という条件を加えたものです。

1. グラフを隣接リストで作る（\(A \to B\) を追加）。
2. 各頂点の入次数 \(indeg[i]\)（前提の数）を数える。
3. \(indeg[i]=0\) の科目をすべて最小ヒープに入れる（最初から履修可能）。
4. ヒープが空になるまで以下を繰り返す：
   • ヒープから最小番号の科目 \(v\) を取り出し、答えに追加する（履修する）。
   • \(v \to to\) の各辺について、\(indeg[to]\) を \(1\) 減らす。
   • もし \(indeg[to]\) が \(0\) になったら、その科目は新たに履修可能なのでヒープに入れる。
5. 得られた列が求める履修順。

例：\(1\to3,\ 2\to3\) のとき
最初は \(1,2\) が履修可能なのでヒープは \(\{1,2\}\)。最小の \(1\) を履修→次に \(2\)→その後 \(3\) が履修可能、となり順序は \(1,2,3\) になります。

（本問は循環なし・必ず履修可能が保証されるので、必ず \(N\) 個出力されます。）

計算量

• 時間計算量: \(O((N+M)\log N)\)
  （各頂点の push/pop が高々1回ずつで \(O(N\log N)\)、各辺の処理が \(O(M)\)）
• 空間計算量: \(O(N+M)\)
  （隣接リストと入次数配列、ヒープなど）

実装のポイント

• 「履修可能な科目のうち最小番号」を実現するために heapq（最小ヒープ）を使う。

• 入力が最大 \(2\times 10^5\) 行になるので、sys.stdin.buffer.read() でまとめて読み取ると高速。

• グラフは g[a].append(b) の隣接リスト、入次数は indeg[b] += 1 で管理する。

• 辺をたどって indeg[to] が \(0\) になった瞬間にヒープへ入れることで、毎回の全探索を避ける。

  ソースコード

import sys
import heapq

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, M = data[0], data[1]
    g = [[] for _ in range(N + 1)]
    indeg = [0] * (N + 1)

    idx = 2
    for _ in range(M):
        a = data[idx]
        b = data[idx + 1]
        idx += 2
        g[a].append(b)
        indeg[b] += 1

    pq = []
    for i in range(1, N + 1):
        if indeg[i] == 0:
            heapq.heappush(pq, i)

    order = []
    while pq:
        v = heapq.heappop(pq)
        order.append(v)
        for to in g[v]:
            indeg[to] -= 1
            if indeg[to] == 0:
                heapq.heappush(pq, to)

    sys.stdout.write(" ".join(map(str, order)))

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。