210. Course Schedule II

Medium

Description

共有 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#

和 Course Schedule I 一樣偵測環，但額外記錄拓撲排序的順序。

本題是 207 的延伸，不只判斷能否完成，還要輸出一個合法順序
BFS（Kahn’s）直接記錄出隊順序就是拓撲排序
DFS 則需在後序（完成處理後）加入結果，最後反轉

Approaches#

1: DFS（後序 + 反轉）#

概念: DFS 完成節點時加入結果列表，最後反轉得到拓撲順序
時間複雜度: O(V + E)
空間複雜度: 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）#

概念: 入度為 0 的節點先出隊，出隊順序即為拓撲排序
時間複雜度: O(V + E)
空間複雜度: 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 後序反轉
關鍵技巧: DFS 的後序加入結果需要反轉；BFS 的出隊順序直接就是正確的拓撲順序