210. Course Schedule II
解題說明
Course Schedule II
題目描述：給定 numCourses 門課程（編號 0 到 numCourses-1）以及先修要求陣列 prerequisites，其中 prerequisites[i] = [ai, bi] 表示選修課程 ai 前必須先修完課程 bi。請回傳一個合法的修課順序；若存在循環依賴（無法完成所有課程），則回傳空陣列。
解題思路：此題是拓撲排序的經典應用。我們將課程視為有向圖的節點，先修關係視為有向邊，問題等價於「找出有向無環圖（DAG）的拓撲排序，若圖有環則無解」。
使用 Kahn's Algorithm（BFS 版拓撲排序）：
- 建圖：建立每個節點的入度（in-degree）陣列與鄰接表（adjacency list）。
prerequisites[i] = [a, b]代表邊 b → a，因此adj[b].push_back(a)且indegree[a]++。 - 初始化佇列：將所有入度為 0 的節點（無先修課程的課）加入 BFS 佇列。
- BFS 處理：每次從佇列取出一個節點，將其加入修課順序。對其所有鄰居節點減少入度，若鄰居入度降為 0，則加入佇列。
- 檢查結果：若最終收集到的修課順序長度等於
numCourses，則回傳此順序；否則代表圖中有環，回傳空陣列。
Kahn's Algorithm 的直覺：入度為 0 的節點表示「所有先修課程已完成」，可以安全修讀。每修完一門課，相當於移除這條邊，更新後續課程的入度。
C++ 解法
複雜度分析
時間複雜度：O(V + E) — 其中 V = numCourses（節點數），E = prerequisites.size()（邊數）。建圖需要 O(E)，BFS 每個節點和每條邊各處理一次，共需 O(V + E)。
空間複雜度：O(V + E) — 鄰接表儲存所有邊需要 O(E)，入度陣列和修課順序各需 O(V)，BFS 佇列最壞情況下需要 O(V)。
虛擬碼
1. Build adjacency list adj[] and indegree[] array from prerequisites
- For each [course, prereq]: adj[prereq].append(course), indegree[course]++
2. Initialize BFS queue with all nodes where indegree[i] == 0
3. While queue is not empty:
a. Dequeue node, append to order[]
b. For each neighbor of node:
- Decrement indegree[neighbor]
- If indegree[neighbor] == 0: enqueue neighbor
4. If len(order) == numCourses: return order
5. Else: return [] (cycle detected)其他解法
DFS 後序拓撲排序 O(V+E)：使用 DFS 並追蹤三種節點狀態（未訪問、訪問中、已完成）。若在 DFS 過程中遇到「訪問中」的節點，表示存在環，回傳空陣列。否則在後序（post-order）時將節點加入結果，最後反轉即為拓撲順序。與 Kahn's Algorithm 相比，DFS 版本更直覺地對應「遞迴展開」的概念，但需要額外維護狀態陣列。
Union-Find 環偵測 O(E·α(V))：可用於偵測是否有環，但無法直接給出拓撲順序。適合只需判斷「能否修完所有課程」的 Course Schedule I，不適用於本題需要輸出具體順序的需求。
延伸思考
- 若課程之間存在多個合法的修課順序，是否有辦法找出所有合法排列？時間複雜度會如何變化？
- 如果加入限制：同一時間可以平行修讀多門課（無先修依賴的課），最少需要幾個「學期」才能修完所有課程？（提示：這是 LeetCode 1136 Parallel Courses 的延伸）
- 若先修關係形成一棵樹而非一般有向圖，拓撲排序的演算法能否進一步優化？有哪些特殊性質可以利用？