LeetCode 210 Course Schedule II：拓撲排序 BFS (Kahn 算法) 輸出修課順序

題目與模型

n 門課（0..n-1），prerequisites 給出先修關係 [a, b] 表示 b → a（修完 b 才能修 a）。求任一合法修課順序（拓撲序），若有環返回空陣列。

Kahn 算法 (BFS 拓撲排序)

1. 建圖：adj[b].push_back(a)，統計入度 inDeg[a]++。
2. 佇列初始化：所有 inDeg[i] == 0 入隊。
3. 循環：取出 u，加入答案；遍歷 adj[u]，inDeg[v]--，若變 0 入隊。
4. 若最終答案長度 < n，說明有環，返回空。

工程細節：去重邊與自環

輸入可能含平行邊或自環（a == b）。代碼中用 find 檢查 adj[b] 是否已含 a，避免重複計入度。自環直接返回空。

參考代碼

class Solution {
public:
    vector findOrder(int numCourses, vector>& prerequisites) {
        vector> adj(numCourses);
        vector inDeg(numCourses, 0);
        for (auto [a, b] : prerequisites) {
            if (a == b) return {}; // self-loop
            if (find(adj[b].begin(), adj[b].end(), a) == adj[b].end()) {
                adj[b].push_back(a);
                ++inDeg[a];
            }
        }
        queue q;
        for (int i = 0; i < numCourses; ++i) if (inDeg[i] == 0) q.push(i);
        vector order;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            order.push_back(u);
            for (int v : adj[u]) if (--inDeg[v] == 0) q.push(v);
        }
        return order.size() == numCourses ? order : vector{};
    }
};

複雜度

• 時間 O(V + E)（去重用 find 使邊處理為 O(E × deg)，實際可改用 unordered_set 優化至 O(E)）。
• 空間 O(V + E)。

總結

本題是拓撲排序輸出具體順序的標準應用。Kahn 算法直觀易實現，關鍵在於正確構建圖、處理入度、檢測環。工程上需注意輸入可能含重複邊/自環，做去重與防禦性判斷。