題目描述:
共有 numCourses 門課(編號 0 到 numCourses-1),以及先修關係 prerequisites。給定一組查詢 queries,對每個查詢 [u, v],判斷課程 u 是否為課程 v 的先修課(直接或間接)。
解題思路:
使用 Floyd-Warshall 演算法的變體(傳遞閉包)。建立一個 n x n 的 boolean 矩陣 reachable,其中 reachable[i][j] 表示從課程 i 可以到達課程 j。
此方法適合查詢量大的情況,因為預處理 O(n^3) 後,每次查詢 O(1)。
時間複雜度: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 resultBFS/DFS 對每個節點:對每個節點做 BFS/DFS,找出它能到達的所有節點。時間 O(n * (n + E)),適合邊數少的稀疏圖。
拓撲排序 + Bitset:拓撲排序後,用 bitset 紀錄每個節點的所有祖先。沿拓撲序傳播祖先資訊。時間 O(n^2 / 64 + E),利用位元平行化加速,適合 n 較大的情況。