LeetCode 210 課程表 II：拓撲排序輸出合法學習順序

問題描述

在 Course Schedule I 判斷能否完成基礎上，要求輸出一個合法的學習順序（拓撲序列）。若不可能（有環），返回空數組。

核心算法：Kahn 算法 (BFS 拓撲排序) + 記錄順序

與 Course Schedule I 相同，但在 BFS 過程中將出隊節點加入結果列表。最終若結果長度 == numCourses，返回結果；否則返回空。

關鍵代碼 (Java)

public int[] findOrder(int numCourses, int[][] prerequisites) {
    List> adj = new ArrayList<>();
    for (int i = 0; i < numCourses; ++i) adj.add(new ArrayList<>());
    int[] indegree = new int[numCourses];

    for (int[] pre : prerequisites) {
        adj.get(pre[1]).add(pre[0]); // pre[1] -> pre[0]
        indegree[pre[0]]++;
    }

    Queue q = new LinkedList<>();
    for (int i = 0; i < numCourses; ++i)
        if (indegree[i] == 0) q.offer(i);

    List order = new ArrayList<>();
    while (!q.isEmpty()) {
        int u = q.poll();
        order.add(u);
        for (int v : adj.get(u)) {
            if (--indegree[v] == 0) q.offer(v);
        }
    }

    if (order.size() == numCourses)
        return order.stream().mapToInt(i -> i).toArray();
    return new int[0];
}

複雜度分析

• 時間：O(V + E)。
• 空間：O(V + E)。

關鍵點總結

• 圖建模：[a,b] 表示 b → a。
• 入度為 0 入隊：無先修課程的課優先學習。
• 輸出順序：出隊順序即為合法拓撲序（可能有多解，任意一個即可）。
• 環檢測：結果長度 < numCourses ⇔ 有環 ⇔ 返回空數組。

DFS 版本（補充）

DFS 後序遍歷逆序也可得拓撲序。需三色標記檢測環。

總結

LeetCode 210 是拓撲排序輸出序列的標準模板。掌握 Kahn 算法（BFS）和 DFS 後序逆序兩種方法，可解決所有「任務調度輸出順序、編譯依賴順序」問題。BFS 版本更直觀且易於並行化。