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) 更好的方法？