Course Schedule IV
Problem
n courses 0..n-1 and prerequisites edges a→b. Answer each query (u, v): is u a prerequisite of v (directly or transitively)?
n=3, prerequisites=[[1,2],[1,0],[2,0]], queries=[[1,0],[1,2]][true,true]def check_if_prerequisite(n, prerequisites, queries):
reach = [[False]*n for _ in range(n)]
for a, b in prerequisites: reach[a][b] = True
for k in range(n):
for i in range(n):
for j in range(n):
if reach[i][k] and reach[k][j]: reach[i][j] = True
return [reach[u][v] for u, v in queries]function checkIfPrerequisite(n, prerequisites, queries) {
const reach = Array.from({length: n}, () => new Array(n).fill(false));
for (const [a, b] of prerequisites) reach[a][b] = true;
for (let k = 0; k < n; k++) for (let i = 0; i < n; i++) for (let j = 0; j < n; j++)
if (reach[i][k] && reach[k][j]) reach[i][j] = true;
return queries.map(([u, v]) => reach[u][v]);
}class Solution {
public List checkIfPrerequisite(int n, int[][] pr, int[][] q) {
boolean[][] r = new boolean[n][n];
for (int[] e : pr) r[e[0]][e[1]] = true;
for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++)
if (r[i][k] && r[k][j]) r[i][j] = true;
List ans = new ArrayList<>();
for (int[] x : q) ans.add(r[x[0]][x[1]]);
return ans;
}
} vector checkIfPrerequisite(int n, vector>& pr, vector>& q) {
vector> r(n, vector(n, false));
for (auto& e : pr) r[e[0]][e[1]] = true;
for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++)
if (r[i][k] && r[k][j]) r[i][j] = true;
vector a;
for (auto& x : q) a.push_back(r[x[0]][x[1]]);
return a;
} Explanation
Each query asks whether course u is a prerequisite of v, directly or through a chain. Instead of searching per query, we precompute a full reachability matrix once and then answer every query in constant time.
The matrix reach[i][j] means "i can reach j". We start by marking the direct edges from prerequisites. Then we run a Floyd–Warshall-style triple loop to close it under transitivity.
The key line is if reach[i][k] and reach[k][j]: reach[i][j] = True. It says: if i can reach some middle node k, and k can reach j, then i can reach j too. Looping k over every node as a possible stepping stone fills in all indirect paths.
Example: edges 1→2 and 2→0. When k=2, we see reach[1][2] and reach[2][0] are both true, so we set reach[1][0]=True — capturing the indirect chain 1→2→0.
After the matrix is complete, each query (u, v) is just a direct lookup of reach[u][v], so all answers come back immediately.