概要

この問題は、タスク間の「先にやるべき」という依存関係を満たしつつ、実行順序を辞書順最小にする問題です。
グラフの トポロジカルソート を行い、毎回「今実行できるタスクの中で番号が最小のもの」を選べば解けます。

考察

各条件「タスク \(A_i\) をタスク \(B_i\) より先に行う」は、
有向辺 \(A_i \to B_i\) と考えることができます。

すると問題は、

• 有向グラフに対して
• すべての辺の向きを守るように頂点を並べる
• その中で辞書順最小の並びを求める

という形になります。
これはまさに トポロジカルソート の問題です。

重要な観察

ある時点で実行できるタスクは、
まだ終わっていないタスクのうち、前提条件をすべて満たしているもの です。

グラフで言うと、これは 入次数が \(0\) の頂点 に対応します。
なぜなら、そのタスクに入ってくる辺がない = 「まだ終わっていない前提タスクがない」からです。

辞書順最小にするには？

普通のトポロジカルソートでは、入次数 \(0\) の頂点をどれから取っても正しい順序になります。
しかし今回は 辞書順最小 にしたいので、

• 実行可能なタスクが複数あるなら
• 番号が最小のものを必ず選ぶ

必要があります。

この操作を効率よく行うために、入次数 \(0\) の頂点を 最小ヒープ で管理します。

素朴な方法がなぜだめか

たとえば毎回

1. 全タスクを見て入次数 \(0\) のものを探す
2. その中で最小番号を選ぶ

とすると、各ステップで \(O(N)\) かかり、全体で \(O(N^2)\) になります。
\(N \leq 2 \times 10^5\) なので、これは間に合いません。

そこで、

• 入次数を配列で管理する
• 入次数が \(0\) になったタスクをヒープに入れる
• ヒープから最小番号を取り出す

という形にすると、高速に処理できます。

実行不可能な場合

前提条件に矛盾があると、グラフの中に 閉路 ができます。

例: - \(1 \to 2\) - \(2 \to 3\) - \(3 \to 1\)

この場合、どのタスクも誰かを先にやる必要があり、最初に始められるタスクがありません。
トポロジカルソートでは、最終的に並べられた頂点数が \(N\) 未満になります。
そのときは -1 を出力すればよいです。

アルゴリズム

以下の手順で求めます。

1. グラフを隣接リストで構築する

   • 辺 \(A_i \to B_i\) を追加
   • 同時に \(B_i\) の入次数を \(1\) 増やす

2. 入次数が \(0\) のタスクをすべて最小ヒープに入れる

3. ヒープが空になるまで以下を繰り返す

   • ヒープから最小のタスク番号 \(v\) を取り出す
   • 答えに追加する
   • \(v\) から出る辺 \(v \to nv\) について
     • \(nv\) の入次数を \(1\) 減らす
     • 入次数が \(0\) になったらヒープに入れる

4. 最後に、答えに入ったタスク数を確認する

   • \(N\) 個ならその順序を出力
   • \(N\) 個未満なら閉路があるので -1

具体例

例えば

• \(1 \to 3\)
• \(2 \to 3\)

のとき、最初にできるのは \(1, 2\) です。
辞書順最小にするには、まず \(1\) を選びます。
次にまだ \(2\) が選べるので \(2\) を選び、最後に \(3\) が選べます。

よって答えは
\(1, 2, 3\)
になります。

もしヒープを使わず適当に選ぶと \(2,1,3\) になることもありますが、これは辞書順最小ではありません。

計算量

• 時間計算量: \(O((N + M)\log N)\)
• 空間計算量: \(O(N + M)\)

実装のポイント

• グラフは adj[a].append(b) の形で隣接リストにする
• 入次数は indeg[b] += 1 で管理する
• 辞書順最小にするため、入次数 \(0\) の頂点集合は キューではなく最小ヒープ を使う
• 最後に len(order) != n なら、閉路があって実行不可能なので -1 を出力する

このコードはまさにその方針をそのまま実装したものです。

ソースコード

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]
    adj = [[] for _ in range(n + 1)]
    indeg = [0] * (n + 1)

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

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

    order = []
    while h:
        v = heapq.heappop(h)
        order.append(v)
        for nv in adj[v]:
            indeg[nv] -= 1
            if indeg[nv] == 0:
                heapq.heappush(h, nv)

    if len(order) != n:
        print(-1)
    else:
        print(*order)

if __name__ == "__main__":
    main()

---

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