O(V^3 + Q) O(V^2)
Intuition
Precompute for every pair (i, j) whether i is a (direct or indirect) prerequisite of j. That's the transitive closure of the prerequisite graph, which Floyd-Warshall computes in O(V^3); each query is then an O(1) lookup.
Explanation
Precompute all reachability
Each query asks whether u reaches v through prerequisite edges. Rather than search per query, compute the full transitive closure: a boolean matrix reach[i][j] that is true when i is a prerequisite of j.
Floyd-Warshall closure
Start with the direct edges, then let every course k act as an intermediate hop:
for a, b in prerequisites: reach[a][b] = true
for k in 0..V-1:
for i in 0..V-1:
if reach[i][k]:
for j in 0..V-1:
if reach[k][j]: reach[i][j] = true
answer = [reach[u][v] for u, v in queries]
If i reaches k and k reaches j, then i reaches j. After the triple loop, reach holds every indirect prerequisite.
Worked example
numCourses = 5, chain 0->1->2->3->4.
Closure makes reach[0][*] true for 1,2,3,4, etc. Queries:
[0,4]→0is a prerequisite of4→ true.[4,0]→4is not a prerequisite of0→ false.[1,3]→ true;[3,0]→ false.
answer = [true, false, true, false].
Complexity
- Time: O(V^3 + Q) for the closure plus O(1) per query.
- Space: O(V^2) for the reachability matrix.
Implementation
class Solution {
public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
boolean[][] reach = new boolean[numCourses][numCourses];
for (int[] p : prerequisites) {
reach[p[0]][p[1]] = true;
}
for (int k = 0; k < numCourses; k++) {
for (int i = 0; i < numCourses; i++) {
if (reach[i][k]) {
for (int j = 0; j < numCourses; j++) {
if (reach[k][j]) reach[i][j] = true;
}
}
}
}
List<Boolean> ans = new ArrayList<>();
for (int[] q : queries) {
ans.add(reach[q[0]][q[1]]);
}
return ans;
}
}