概要

タスク間の「先にやるべき」関係は有向グラフとして表せるため、この問題は辞書順最小のトポロジカルソートを求める問題です。
入次数 \(0\) の頂点（今すぐ実行可能なタスク）のうち、常に最小番号を選べば辞書順最小になります。

考察

前提条件「\(A_i\) を \(B_i\) より先に実行」は、有向辺 \(A_i \to B_i\) と見なせます。
すると、条件を満たす実行順序は「有向グラフのトポロジカル順序」です。

重要な気づき

• ある時点で実行可能なのは、未実行タスクの中で入次数が \(0\) のもの。
• 辞書順最小にしたいなら、その候補の中で最小番号を毎回選べばよい（貪欲）。

素朴解が難しい理由

• 毎回「実行可能な最小番号タスク」を線形探索すると、最悪で \(O(N^2)\) になりうる。
• \(N, M \le 2 \times 10^5\) なので \(O(N^2)\) は間に合いません。

解決策

• 入次数 \(0\) の頂点集合を 最小ヒープ で管理する。
• これにより、最小番号の取り出しが \(O(\log N)\) でできる。
• 辺をたどって入次数を減らし、\(0\) になったらヒープに追加する。

また、最後に取り出したタスク数が \(N\) 未満なら、どこかに閉路があり実行不可能なので -1 を出力します。

アルゴリズム

1. 隣接リスト graph と各頂点の入次数 indeg を作る。
   各条件 \((a,b)\) に対して:
   • graph[a].append(b)
   • indeg[b] += 1
2. 入次数が \(0\) の全頂点を最小ヒープ pq に入れる。
3. pq が空になるまで繰り返す：
   • 最小の頂点 v を取り出して答え order に追加
   • v から出る各辺 v -> nv について indeg[nv] -= 1
   • indeg[nv] == 0 になったら pq に追加
4. order の長さが \(N\) ならそのまま出力、そうでなければ -1 を出力。

この手順は「Kahn 法（トポロジカルソート）」に、辞書順最小化のための最小ヒープを組み合わせたものです。

計算量

• 時間計算量: \(O((N+M)\log N)\)
  （各頂点のヒープ操作と、各辺の入次数更新）
• 空間計算量: \(O(N+M)\)
  （隣接リスト、入次数配列、ヒープ、答え配列）

実装のポイント

• 頂点番号が \(1\) から \(N\) なので、配列サイズは N+1 にする。

• 辞書順最小化の要は heapq（最小ヒープ）。deque では辞書順最小は保証できません。

• 閉路判定は len(order) != N で簡潔にできる。
  これは「入次数 \(0\) が尽きたのに未処理頂点が残る」ことを意味します。

  ソースコード

import sys
import heapq

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    
    graph = [[] for _ in range(N + 1)]
    indeg = [0] * (N + 1)
    
    for _ in range(M):
        a, b = map(int, input().split())
        graph[a].append(b)
        indeg[b] += 1
    
    pq = []
    for v in range(1, N + 1):
        if indeg[v] == 0:
            heapq.heappush(pq, v)
    
    order = []
    while pq:
        v = heapq.heappop(pq)
        order.append(v)
        for nv in graph[v]:
            indeg[nv] -= 1
            if indeg[nv] == 0:
                heapq.heappush(pq, nv)
    
    if len(order) != N:
        print(-1)
    else:
        print(*order)

if __name__ == "__main__":
    main()

---

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