概要

この問題は、前提条件付きの科目を番号が小さい順に選択しながらトポロジカルソートを行う問題です。

考察

前提条件を有向辺としてグラフを構築すると、これは有向非巡回グラフ(DAG)になります。各ステップで「前提科目をすべて履修済みの科目」とは、グラフにおいて入次数が0のノードに対応します。問題では、その中で番号が最も小さいものを選ぶ必要があるため、単純なキューではなく最小の要素を効率的に取り出せるデータ構造が必要です。

素朴なアプローチとして、各ステップで入次数0の科目を全探索して最小のものを選ぶ方法が考えられますが、これでは時間計算量が \(O(N^2)\) となり、制約 \(N \leq 2 \times 10^5\) では実行時間が間に合いません。

アルゴリズム

この問題は「優先度付きキューを用いたトポロジカルソート」で効率的に解けます。具体的な手順は以下の通りです：

1. グラフを隣接リストで表現し、各ノードの入次数を管理する配列を用意する
2. すべてのノードの中で入次数が0のものを優先度付きキュー（最小ヒープ）に追加する
3. キューが空になるまで以下を繰り返す：
   • キューから最小の要素を取り出し、結果リストに追加する
   • そのノードから出る辺の先のノードの入次数を1減らす
   • 入次数が0になったノードを優先度付きキューに追加する

これにより、常に「履修可能な科目の中から番号が最小のもの」を効率的に選択できます。

計算量

• 時間計算量: \(O((N + M) \log N)\)
  • 各ノードと辺を1回ずつ処理し、優先度付きキューへの操作が \(\log N\) かかるため
• 空間計算量: \(O(N + M)\)
  • グラフの表現と入次数の管理に必要なメモリ

実装のポイント

• 優先度付きキューにはPythonのheapqモジュールを使用（最小ヒープを提供）

• 入力の読み込みはsys.stdin.read()で一括処理し、高速化

• グラフは0-indexedではなく1-indexedで管理（科目番号が1から始まるため）

• 各ノードを処理する際、そのノードから出る辺の先のノードの入次数を減らし、0になったらキューに追加

  ソースコード

import heapq
import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    n = int(data[0])
    m = int(data[1])
    
    graph = [[] for _ in range(n+1)]
    in_degree = [0] * (n+1)
    
    index = 2
    for _ in range(m):
        a = int(data[index])
        b = int(data[index+1])
        index += 2
        graph[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:
        current = heapq.heappop(heap)
        result.append(current)
        
        for neighbor in graph[current]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                heapq.heappush(heap, neighbor)
    
    print(" ".join(map(str, result)))

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。