LeetCode Course Schedule II：拓撲排序 BFS (Kahn) 求課程順序

問題描述

n 門課，先修關係 [a, b] 表示修 a 前需修 b。返回任意合法修課順序，無解返回空數組。

拓撲排序 (Kahn 算法)

1. 建圖：鄰接表 graph，入度數組 indeg
2. 隊列存入度為 0 的節點
3. 循環：取出節點加入結果，遍歷其出邊減少鄰居入度，入度變 0 入隊
4. 若結果長度 n，返回結果；否則有環，返回空

優化：反向圖 + 集合 (原文思路 2)

維護「未選節點集合」，每次從中找入度 0 的節點。用反向圖快速更新入度。代碼較長，此處給出標準 Kahn 實現。

標準 C++ 實現

vector findOrder(int numCourses, vector>& prerequisites) {
    vector> graph(numCourses);
    vector indeg(numCourses, 0);
    for (auto &e : prerequisites) {
        graph[e[1]].push_back(e[0]);
        ++indeg[e[0]];
    }
    queue q;
    for (int i=0; i order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : graph[u])
            if (--indeg[v] == 0) q.push(v);
    }
    if (order.size() == numCourses) return order;
    return {};
}

複雜度

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

DFS 版（後序遍歷 + 環檢測）

三色標記：0=未訪問，1=訪問中，2=已完成。DFS 返回時壓入棧，最終逆序即拓撲序。檢測到灰色節點（狀態 1）即有環。