共有
numCourses門課，prerequisites[i] = [a, b]表示修課a前需先修b。回傳一個合法的修課順序。若無法完成所有課程，回傳空陣列。
Example:
Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] Output: [0,2,1,3] 或 [0,1,2,3]
Intuition
TIP
和 Course Schedule I 一樣偵測環，但額外記錄拓撲排序的順序。
- 本題是 207 的延伸，不只判斷能否完成，還要輸出一個合法順序
- BFS（Kahn’s）直接記錄出隊順序就是拓撲排序
- DFS 則需在後序（完成處理後）加入結果，最後反轉
Approaches
1. DFS (postorder + reverse) — O(V + E) / O(V + E)
- Idea: DFS 完成節點時加入結果列表，最後反轉得到拓撲順序
- Time:
O(V + E) - Space:
O(V + E)
class Solution {
fun findOrder(numCourses: Int, prerequisites: Array<IntArray>): IntArray {
val graph = Array(numCourses) { mutableListOf<Int>() }
for ((a, b) in prerequisites) graph[b].add(a)
val state = IntArray(numCourses) // 0: unvisited, 1: visiting, 2: visited
val result = mutableListOf<Int>()
fun dfs(node: Int): Boolean {
if (state[node] == 1) return false
if (state[node] == 2) return true
state[node] = 1
for (next in graph[node]) {
if (!dfs(next)) return false
}
state[node] = 2
result.add(node)
return true
}
for (i in 0 until numCourses) {
if (!dfs(i)) return intArrayOf()
}
return result.reversed().toIntArray()
}
}⭐ 2. BFS（Kahn's Algorithm） — O(V + E) / O(V + E)
- Idea: 入度為 0 的節點先出隊，出隊順序即為拓撲排序
- Time:
O(V + E) - Space:
O(V + E)
class Solution {
fun findOrder(numCourses: Int, prerequisites: Array<IntArray>): IntArray {
val graph = Array(numCourses) { mutableListOf<Int>() }
val inDegree = IntArray(numCourses)
for ((a, b) in prerequisites) {
graph[b].add(a)
inDegree[a]++
}
val queue: ArrayDeque<Int> = ArrayDeque()
for (i in 0 until numCourses) {
if (inDegree[i] == 0) queue.add(i)
}
val order = IntArray(numCourses)
var idx = 0
while (queue.isNotEmpty()) {
val cur = queue.removeFirst()
order[idx++] = cur
for (next in graph[cur]) {
inDegree[next]--
if (inDegree[next] == 0) queue.add(next)
}
}
return if (idx == numCourses) order else intArrayOf()
}
}🔑 Takeaways
- Pattern: 拓撲排序輸出順序 — Kahn’s BFS 出隊順序 / DFS 後序反轉
- Key trick: DFS 的後序加入結果需要反轉；BFS 的出隊順序直接就是正確的拓撲順序