1462. Course Schedule IV

Medium
Description

有 numCourses 門課程和先修關係 prerequisites。給定查詢 queries[i] = [u, v]，回答 u 是否是 v 的直接或間接先修課。

Example:

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

Intuition#

預處理所有節點間的可達性關係，再 O(1) 回答每個查詢。

  • 需要知道任意兩節點間的可達性
  • 可以用 Floyd-Warshall 的思想，或對每個節點做 BFS/DFS
  • 預處理完後，每個查詢只要 O(1) 查表

Approaches#

1: BFS 預處理#

  • 概念: 對每個節點做 BFS，建立可達節點集合
  • 時間複雜度: O(V * (V + E) + Q)
  • 空間複雜度: O(V^2)
class Solution {
    fun checkIfPrerequisite(numCourses: Int, prerequisites: Array<IntArray>, queries: Array<IntArray>): List<Boolean> {
        val graph = Array(numCourses) { mutableListOf<Int>() }
        for ((u, v) in prerequisites) {
            graph[u].add(v)
        }

        val reachable = Array(numCourses) { BooleanArray(numCourses) }
        for (start in 0 until numCourses) {
            val queue = ArrayDeque<Int>()
            queue.add(start)
            reachable[start][start] = true
            while (queue.isNotEmpty()) {
                val node = queue.removeFirst()
                for (next in graph[node]) {
                    if (!reachable[start][next]) {
                        reachable[start][next] = true
                        queue.add(next)
                    }
                }
            }
        }

        return queries.map { (u, v) -> reachable[u][v] }
    }
}

⭐2: 拓撲排序 + 傳遞閉包#

  • 概念: 按拓撲順序處理節點，每個節點繼承所有前驅的可達集合
  • 時間複雜度: O(V^2 + E + Q)
  • 空間複雜度: O(V^2)
class Solution {
    fun checkIfPrerequisite(numCourses: Int, prerequisites: Array<IntArray>, queries: Array<IntArray>): List<Boolean> {
        val graph = Array(numCourses) { mutableListOf<Int>() }
        val inDeg = IntArray(numCourses)
        for ((u, v) in prerequisites) {
            graph[u].add(v)
            inDeg[v]++
        }

        val isPrereq = Array(numCourses) { BooleanArray(numCourses) }
        val queue = ArrayDeque<Int>()
        for (i in 0 until numCourses) {
            if (inDeg[i] == 0) queue.add(i)
        }

        while (queue.isNotEmpty()) {
            val u = queue.removeFirst()
            for (v in graph[u]) {
                // u 是 v 的先修課，u 的所有先修也是 v 的先修
                isPrereq[u][v] = true
                for (i in 0 until numCourses) {
                    if (isPrereq[i][u]) isPrereq[i][v] = true
                }
                inDeg[v]--
                if (inDeg[v] == 0) queue.add(v)
            }
        }

        return queries.map { (u, v) -> isPrereq[u][v] }
    }
}

🔑 Takeaways#

  • Pattern: 傳遞閉包 – 預處理所有節點間的可達性
  • 關鍵技巧: 拓撲排序確保處理節點時，所有前驅已經被處理完畢，可以正確傳遞可達性