概要

\(N\) 個のタスクに前提条件（依存関係）が与えられたとき、すべての前提条件を満たす実行順序のうち辞書順最小のものを求める問題です。これはトポロジカルソートの応用問題です。

考察

問題の本質：トポロジカルソート

「タスク \(A_i\) を タスク \(B_i\) より先に」という関係は、有向グラフの辺 \(A_i \to B_i\) として表現できます。すべての前提条件を満たす順序を求めることは、このグラフのトポロジカルソートに他なりません。

閉路がある場合

もし有向グラフに閉路（サイクル）があると、例えば「タスク1→タスク2→タスク3→タスク1」のように循環依存が発生し、どのタスクも先に実行できません。この場合は -1 を出力します。

辞書順最小にするには？

通常のトポロジカルソート（BFS ベースの Kahn のアルゴリズム）では、入次数が 0 のノード（前提条件をすべて満たしたタスク）をキューから取り出して処理します。

このキューを最小ヒープ（優先度付きキュー）に置き換えれば、毎回「実行可能なタスクのうち番号が最小のもの」を選ぶことができ、辞書順最小の順序が得られます。

例えば、\(N=4\)、前提条件が「3→1」「3→2」の場合： 1. 入次数 0 のタスク：{3, 4} → 最小の 3 を選ぶ 2. タスク3完了後、入次数 0：{1, 2, 4} → 最小の 1 を選ぶ 3. 残り：{2, 4} → 2 を選ぶ 4. 残り：{4} → 4 を選ぶ 5. 結果：3 1 2 4

アルゴリズム

Kahn のアルゴリズム（BFS ベースのトポロジカルソート） をヒープで拡張します。

1. グラフ構築: 各辺 \(A_i \to B_i\) を隣接リストで持ち、各ノードの入次数（indegree）を計算する。
2. 初期化: 入次数が 0 のノードをすべて最小ヒープに追加する。
3. ループ: ヒープが空になるまで以下を繰り返す：
   • ヒープから最小のノード \(u\) を取り出し、結果列に追加する。
   • \(u\) から出る辺の先のノード \(v\) について、\(v\) の入次数を 1 減らす。
   • \(v\) の入次数が 0 になったらヒープに追加する。
4. 判定: 結果列の長さが \(N\) なら出力、\(N\) 未満なら閉路があるので -1 を出力する。

計算量

• 時間計算量: \(O((N + M) \log N)\)
  • 各ノードは最大 1 回ヒープに挿入・削除される（\(O(N \log N)\)）
  • 各辺は 1 回走査される（\(O(M)\)、辺の処理時にヒープ操作が発生すると \(O(M \log N)\)）
• 空間計算量: \(O(N + M)\)
  • グラフの隣接リスト、入次数配列、ヒープ、結果配列の合計

実装のポイント

• 最小ヒープの利用: Python の heapq はデフォルトで最小ヒープなので、そのまま使えば番号が小さいタスクから取り出せます。

• 閉路検出: トポロジカルソートで処理されたノード数が \(N\) に満たなければ閉路が存在します。別途 DFS などで閉路検出をする必要はありません。

• 高速入力: \(N + M\) が最大 \(2 \times 10^5\) になるため、sys.stdin.readline を使って入力を高速化しています。

  ソースコード

import heapq
import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    graph = [[] for _ in range(N + 1)]
    indegree = [0] * (N + 1)
    for _ in range(M):
        a, b = map(int, input().split())
        graph[a].append(b)
        indegree[b] += 1
    
    heap = []
    for i in range(1, N + 1):
        if indegree[i] == 0:
            heapq.heappush(heap, i)
    
    result = []
    while heap:
        u = heapq.heappop(heap)
        result.append(u)
        for v in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                heapq.heappush(heap, v)
    
    if len(result) == N:
        print(*result)
    else:
        print(-1)

main()

---

この解説は claude4.6opus-thinking によって生成されました。