207. Course Schedule

Medium

Description

共有 numCourses 門課（編號 0 到 numCourses - 1），prerequisites[i] = [a, b] 表示修課 a 前需先修 b。判斷是否能修完所有課程（即有向圖中是否存在環）。

Example:

Input: numCourses = 2, prerequisites = [[1,0]] Output: true

Intuition#

課程依賴是有向圖，能修完所有課 = 圖中無環 = 可以進行拓撲排序。

將課程和先修關係建模為有向圖
若圖中有環，代表存在循環依賴，無法完成所有課程
判斷有向圖是否有環：BFS（Kahn’s algorithm）或 DFS 偵測回邊

Approaches#

1: DFS（環偵測）#

概念: 用三色標記法（未訪問/處理中/已完成）偵測有向圖中的環
時間複雜度: O(V + E)
空間複雜度: 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 – 拓撲排序）#

概念: 計算每個節點的入度，從入度為 0 的節點開始 BFS，逐步移除邊。若最終所有節點都被處理，則無環。
時間複雜度: O(V + E)
空間複雜度: 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 三色標記
關鍵技巧: Kahn’s algorithm 最終 count == V 表示無環；DFS 中 visiting 狀態遇到再次訪問即代表有環