MediumRating 1693
1462. Course Schedule IV
depth-first-searchbreadth-first-searchgraphtopological-sort
解題說明
Course Schedule IV
題目描述:
共有 numCourses 門課(編號 0 到 numCourses-1),以及先修關係 prerequisites。給定一組查詢 queries,對每個查詢 [u, v],判斷課程 u 是否為課程 v 的先修課(直接或間接)。
解題思路:
使用 Floyd-Warshall 演算法的變體(傳遞閉包)。建立一個 n x n 的 boolean 矩陣 reachable,其中 reachable[i][j] 表示從課程 i 可以到達課程 j。
- 先根據 prerequisites 初始化直接先修關係。
- 用三層迴圈計算傳遞閉包:若 i 可達 k 且 k 可達 j,則 i 可達 j。
- 對每個查詢直接查表回答。
此方法適合查詢量大的情況,因為預處理 O(n^3) 後,每次查詢 O(1)。
C++ 解法
複雜度分析
時間複雜度:O(n^3 + Q) — Floyd-Warshall 傳遞閉包 O(n^3),回答 Q 個查詢各 O(1)。
空間複雜度:O(n^2) — boolean 矩陣。
虛擬碼
1. Create n x n boolean matrix reachable (all false)
2. For each prerequisite [u, v]: set reachable[u][v] = true
3. Floyd-Warshall transitive closure:
For k from 0 to n-1:
For i from 0 to n-1:
For j from 0 to n-1:
If reachable[i][k] and reachable[k][j]:
reachable[i][j] = true
4. For each query [u, v]: append reachable[u][v] to result
5. Return result其他解法
BFS/DFS 對每個節點:對每個節點做 BFS/DFS,找出它能到達的所有節點。時間 O(n * (n + E)),適合邊數少的稀疏圖。
拓撲排序 + Bitset:拓撲排序後,用 bitset 紀錄每個節點的所有祖先。沿拓撲序傳播祖先資訊。時間 O(n^2 / 64 + E),利用位元平行化加速,適合 n 較大的情況。
延伸思考
- 若先修關係會動態新增,如何高效更新傳遞閉包?
- 若圖中可能有環(非 DAG),如何偵測並處理?
- 若 n 很大(例如 10^5)但查詢很少,是否有比 O(n^3) 更好的方法?