Day 006-Q4 | トポロジカルソート

問題

$N$ 個のタスクがあり、$M$ 個の依存関係が与えられます。「タスク $A$ はタスク $B$ より前に完了しなければならない」という制約に従って、全タスクを実行可能な順番に並べてください。閉路が存在する場合は -1 を出力してください。

入力形式

N M
A1 B1
...（A → B の依存関係）

制約

$1 \le N \le 10^5$

$0 \le M \le 2\times10^5$

$1 \le A_i, B_i \le N$

$A_i \ne B_i$

入出力例

入力例 1

出力例 1

1 2 3 4

入力例 2

出力例 2

-1

ヒント (段階的開示)

ヒント1: 方向性

DAG の頂点を「依存先がすべて完了してから処理する」順に並べます。

ヒント2: アプローチ

Kahn のアルゴリズム:

全頂点の入次数を計算
入次数 0 の頂点をキューに追加
キューから取り出して処理 → 隣接頂点の入次数を $-1$ → $0$ になったらキューへ
処理数 $< N$ なら閉路あり

ヒント3: 誘導

indegree = [0] * (N + 1)
for a, b in edges:
    indegree[b] += 1
q = deque(v for v in range(1, N+1) if indegree[v] == 0)

模範解答 (Python)

import sys
from collections import deque
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

    q = deque()
    for v in range(1, N + 1):
        if indegree[v] == 0:
            q.append(v)

    order = []
    while q:
        v = q.popleft()
        order.append(v)
        for u in graph[v]:
            indegree[u] -= 1
            if indegree[u] == 0:
                q.append(u)

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

main()

Step-by-Step 解説

1グラフと入次数の初期化
各辺 $A \to B$ に対して indegree[B] += 1。入次数 = 「自分に依存しているタスクの数」。

2キューの初期化
入次数 0（先行タスクなし）の頂点をすべてキューに入れる。「今すぐ実行できる」タスク。

3BFS でトポロジカル順を構築
頂点を取り出すたびに、隣接する頂点の入次数を $-1$。$0$ になったらキューへ。

4閉路判定
全頂点が処理されれば DAG。len(order) < N なら閉路の中に取り残された頂点がある。

よくあるミス

ミス	原因	正しい書き方
閉路判定を忘れる	問題文を読み飛ばす	`len(order) == N` を確認
辺の向きを逆にする	依存関係の解釈ミス	`A→B` = 「A が終わったら B を実行可能」
DFS で閉路判定が複雑	訪問済みフラグ管理が複雑	Kahn アルゴリズムの方がシンプル

次のステップ

発展問題: 最長パス（DAG 上の DP）— 各タスクに時間コストが付いた場合の最小完了時間

自己評価

完全理解おおむね理解要復習

Day 006-Q4 — トポロジカルソート

問題