有
numCourses門課程和先修關係prerequisites。給定查詢queries[i] = [u, v]，回答u是否是v的直接或間接先修課。
Example:
Input: numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]] Output: [false,true]
Intuition
TIP
預處理所有節點間的可達性關係，再 O(1) 回答每個查詢。
- 需要知道任意兩節點間的可達性
- 可以用 Floyd-Warshall 的思想，或對每個節點做 BFS/DFS
- 預處理完後，每個查詢只要 O(1) 查表
Approaches
1. BFS Preprocessing — O(V * (V + E) + Q) / O(V^2)
- Idea: 對每個節點做 BFS，建立可達節點集合
- Time:
O(V * (V + E) + Q) - Space:
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. Topological Sort + Transitive Closure — O(V^2 + E + Q) / O(V^2)
- Idea: 按拓撲順序處理節點，每個節點繼承所有前驅的可達集合
- Time:
O(V^2 + E + Q) - Space:
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: 傳遞閉包 — 預處理所有節點間的可達性
- Key trick: 拓撲排序確保處理節點時，所有前驅已經被處理完畢，可以正確傳遞可達性