共有
numCourses門課（編號0到numCourses - 1），prerequisites[i] = [a, b]表示修課a前需先修b。判斷是否能修完所有課程（即有向圖中是否存在環）。
Example:
Input: numCourses = 2, prerequisites = [[1,0]] Output: true
Intuition
TIP
課程依賴是有向圖，能修完所有課 = 圖中無環 = 可以進行拓撲排序。
- 將課程和先修關係建模為有向圖
- 若圖中有環，代表存在循環依賴，無法完成所有課程
- 判斷有向圖是否有環：BFS（Kahn’s algorithm）或 DFS 偵測回邊
Approaches
1. DFS (cycle detection) — O(V + E) / O(V + E)
- Idea: 用三色標記法（未訪問/處理中/已完成）偵測有向圖中的環
- Time:
O(V + E) - Space:
O(V + E)
class Solution {
fun canFinish(numCourses: Int, prerequisites: Array<IntArray>): Boolean {
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
fun dfs(node: Int): Boolean {
if (state[node] == 1) return false // cycle
if (state[node] == 2) return true
state[node] = 1
for (next in graph[node]) {
if (!dfs(next)) return false
}
state[node] = 2
return true
}
for (i in 0 until numCourses) {
if (!dfs(i)) return false
}
return true
}
}⭐ 2. BFS (Kahn's Algorithm — topological sort) — O(V + E) / O(V + E)
- Idea: 計算每個節點的入度，從入度為 0 的節點開始 BFS，逐步移除邊。若最終所有節點都被處理，則無環。
- Time:
O(V + E) - Space:
O(V + E)
class Solution {
fun canFinish(numCourses: Int, prerequisites: Array<IntArray>): Boolean {
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)
}
var count = 0
while (queue.isNotEmpty()) {
val cur = queue.removeFirst()
count++
for (next in graph[cur]) {
inDegree[next]--
if (inDegree[next] == 0) queue.add(next)
}
}
return count == numCourses
}
}🔑 Takeaways
- Pattern: 有向圖環偵測 / 拓撲排序 — Kahn’s BFS 或 DFS 三色標記
- Key trick: Kahn’s algorithm 最終 count == V 表示無環；DFS 中
visiting狀態遇到再次訪問即代表有環