# Course Schedule IV
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/course-schedule-iv)
Canonical: https://scaleengineer.com/dsa/problems/course-schedule-iv
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Topological Sort](https://scaleengineer.com/algorithms/topological-sort)
**Data structures:** Graph
---
## Problem
There are a total of `numCourses` courses you have to take, labeled from `0` to `numCourses - 1`. You are given an array `prerequisites` where `prerequisites[i] = [ai, bi]` indicates that you **must** take course `ai` first if you want to take course `bi`.

* For example, the pair `[0, 1]` indicates that you have to take course `0` before you can take course `1`.

Prerequisites can also be **indirect**. If course `a` is a prerequisite of course `b`, and course `b` is a prerequisite of course `c`, then course `a` is a prerequisite of course `c`.

You are also given an array `queries` where `queries[j] = [uj, vj]`. For the `jth` query, you should answer whether course `uj` is a prerequisite of course `vj` or not.

Return _a boolean array_ `answer`_, where_ `answer[j]` _is the answer to the_ `jth` _query._

**Example 1:**

![](https://assets.glich.co/dsa/course-schedule-iv/image0.jpg) 

**Input:** numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
**Output:** [false,true]
**Explanation:** The pair [1, 0] indicates that you have to take course 1 before you can take course 0.
Course 0 is not a prerequisite of course 1, but the opposite is true.

**Example 2:**

**Input:** numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]]
**Output:** [false,false]
**Explanation:** There are no prerequisites, and each course is independent.

**Example 3:**

![](https://assets.glich.co/dsa/course-schedule-iv/image1.jpg) 

**Input:** numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]
**Output:** [true,true]

**Constraints:**

* `2 <= numCourses <= 100`
* `0 <= prerequisites.length <= (numCourses * (numCourses - 1) / 2)`
* `prerequisites[i].length == 2`
* `0 <= ai, bi <= numCourses - 1`
* `ai != bi`
* All the pairs `[ai, bi]` are **unique**.
* The prerequisites graph has no cycles.
* `1 <= queries.length <= 104`
* `0 <= ui, vi <= numCourses - 1`
* `ui != vi`

# Approaches
## Brute-Force Traversal for Each Query
This approach treats each query independently. For every query `[u, v]`, it performs a graph traversal, such as Breadth-First Search (BFS) or Depth-First Search (DFS), starting from the course `u`. The goal is to determine if course `v` is reachable from `u`. If `v` is encountered during the traversal, it means `u` is a prerequisite for `v`.
**Time:** O(Q * (N + P)), where Q is `queries.length`. For each of the Q queries, we perform a graph traversal (BFS/DFS) which takes O(N + P) time in the worst case. · **Space:** O(N + P), where N is `numCourses` and P is `prerequisites.length`. This space is used for storing the adjacency list. Each traversal also requires O(N) space for the queue and visited array.
**Pros:** Conceptually simple and straightforward to implement.; Uses less memory than pre-computation approaches, which might be an advantage if memory is severely constrained and the number of queries is small.
**Cons:** Highly inefficient for a large number of queries, as it repeatedly traverses the same parts of the graph.; Very likely to cause a 'Time Limit Exceeded' (TLE) error on platforms with strict time limits due to its high time complexity.
### Explanation
First, we represent the course prerequisites as a directed graph. An adjacency list is a suitable data structure, where `adj[i]` stores a list of courses that have `i` as a direct prerequisite.

The algorithm proceeds as follows:
1.  Construct the adjacency list from the `prerequisites` array.
2.  Initialize a list `answer` to store the results of the queries.
3.  Iterate through each query `[u, v]`.
4.  For the current query, start a BFS (or DFS) from node `u`. A queue is used for BFS, and a `visited` set is maintained to avoid redundant computations and handle the graph structure efficiently.
5.  During the BFS, if we dequeue a node and it is the target node `v`, we have found a path. This confirms that `u` is a prerequisite for `v`. We add `true` to our `answer` list and move to the next query.
6.  If the BFS completes without finding `v`, it means there is no path from `u` to `v`. In this case, `u` is not a prerequisite for `v`, and we add `false` to the `answer` list.
7.  After processing all queries, return the `answer` list.

```java
class Solution {
    public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] p : prerequisites) {
            adj.get(p[0]).add(p[1]);
        }

        List<Boolean> ans = new ArrayList<>();
        for (int[] q : queries) {
            ans.add(isReachable(q[0], q[1], numCourses, adj));
        }
        return ans;
    }

    private boolean isReachable(int startNode, int endNode, int n, List<List<Integer>> adj) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[n];

        queue.offer(startNode);
        visited[startNode] = true;

        while (!queue.isEmpty()) {
            int curr = queue.poll();
            if (curr == endNode) {
                return true;
            }
            for (int neighbor : adj.get(curr)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.offer(neighbor);
                }
            }
        }
        return false;
    }
}
```
### Algorithm
*   Build an adjacency list `adj` where `adj.get(u)` contains a list of courses `v` for which `u` is a direct prerequisite.
*   Initialize an empty list `answer` to store the boolean results.
*   For each query `[u, v]` in the `queries` array:
    *   Perform a Breadth-First Search (BFS) or Depth-First Search (DFS) starting from node `u` to check for reachability to `v`.
    *   To perform BFS:
        *   Initialize a queue and add the starting course `u`.
        *   Use a `visited` boolean array to keep track of visited nodes for the current query to avoid redundant processing.
        *   While the queue is not empty, dequeue a course `current`.
        *   If `current` is the target course `v`, then a path exists. Add `true` to the `answer` list and break the search for this query.
        *   Otherwise, for each `neighbor` of `current` in the adjacency list, if the neighbor has not been visited, mark it as visited and enqueue it.
    *   If the traversal completes without finding `v`, it means `v` is not reachable from `u`. Add `false` to the `answer` list.
*   Return the `answer` list.

## Pre-computation using Floyd-Warshall Algorithm
This approach improves upon the brute-force method by pre-computing all possible prerequisite relationships. The set of all reachability pairs in a graph is known as its transitive closure. The Floyd-Warshall algorithm is a classic dynamic programming algorithm that can compute this transitive closure. After an initial phase of pre-computation, each query can be answered in constant time.
**Time:** O(N^3 + P + Q). The dominant part is the Floyd-Warshall algorithm with its three nested loops, which takes O(N^3). Initializing the matrix takes O(P), and answering all queries takes O(Q). · **Space:** O(N^2) to store the `isReachable` matrix.
**Pros:** Extremely fast query time (O(1)) after the initial setup.; The implementation is relatively simple and consists of straightforward nested loops.; Guaranteed performance regardless of the graph's structure (density).
**Cons:** The O(N^3) time complexity for pre-computation can be slower than other methods if the graph is very sparse (i.e., P is much smaller than N^2).; Requires O(N^2) space, which could be a concern for problems with a very large number of courses.
### Explanation
The core idea is to build a 2D boolean matrix, `isReachable[i][j]`, which will be `true` if course `i` is a prerequisite for course `j` (i.e., `j` is reachable from `i`), and `false` otherwise.

The algorithm works as follows:
1.  Initialize an `N x N` boolean matrix `isReachable`, where `N` is `numCourses`.
2.  Populate the matrix with direct prerequisites: for each pair `[u, v]` in `prerequisites`, set `isReachable[u][v] = true`.
3.  Apply the Floyd-Warshall algorithm. We iterate through all possible courses `k` and consider them as intermediate nodes in a path. For every pair of courses `(i, j)`, if there is a path from `i` to `k` and a path from `k` to `j`, then there must be a path from `i` to `j`. We update `isReachable[i][j]` accordingly. The update rule is: `isReachable[i][j] = isReachable[i][j] || (isReachable[i][k] && isReachable[k][j])`.
4.  After the three nested loops complete, the `isReachable` matrix contains the full transitive closure of the prerequisite graph.
5.  Process the queries. For each query `[u, v]`, the answer is simply the value of `isReachable[u][v]`. This is an O(1) lookup.
6.  Collect the results and return them.

```java
class Solution {
    public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
        boolean[][] isReachable = new boolean[numCourses][numCourses];
        for (int[] p : prerequisites) {
            isReachable[p[0]][p[1]] = true;
        }

        for (int k = 0; k < numCourses; k++) {
            for (int i = 0; i < numCourses; i++) {
                for (int j = 0; j < numCourses; j++) {
                    isReachable[i][j] = isReachable[i][j] || (isReachable[i][k] && isReachable[k][j]);
                }
            }
        }

        List<Boolean> ans = new ArrayList<>();
        for (int[] q : queries) {
            ans.add(isReachable[q[0]][q[1]]);
        }
        return ans;
    }
}
```
### Algorithm
*   Initialize an `N x N` boolean matrix `isReachable`, where `N` is `numCourses`, with all values as `false`.
*   Populate the matrix with direct prerequisites. For each pair `[u, v]` in the `prerequisites` input, set `isReachable[u][v] = true`.
*   Apply the Floyd-Warshall algorithm to find all-pairs reachability. This involves three nested loops:
    *   The outer loop iterates through an intermediate course `k` from `0` to `N-1`.
    *   The two inner loops iterate through all pairs of courses `(i, j)` from `0` to `N-1`.
    *   Inside the loops, update the reachability using the rule: `isReachable[i][j] = isReachable[i][j] || (isReachable[i][k] && isReachable[k][j])`. This checks if a path from `i` to `j` can be formed by passing through `k`.
*   After the loops complete, `isReachable[i][j]` will be `true` if `j` is reachable from `i` (directly or indirectly).
*   For each query `[u, v]`, the answer is a direct O(1) lookup of `isReachable[u][v]`.
*   Collect the results for all queries and return them.

## Pre-computation using Multiple Graph Traversals
This is another pre-computation approach that is often more efficient than Floyd-Warshall, especially for sparse graphs. Instead of using dynamic programming, we explicitly find all reachable nodes for each course by running a separate graph traversal (BFS or DFS) starting from every single course. This builds the same transitive closure information but can be faster depending on the graph's density.
**Time:** O(N * (N + P) + Q). We run N traversals. Each traversal takes at most O(N + P) time. For sparse graphs, this is closer to O(N*P), which is better than Floyd-Warshall's O(N^3). For dense graphs, the complexity approaches O(N^3). · **Space:** O(N^2 + P). We need O(N+P) for the adjacency list and O(N^2) for the `isPrerequisite` matrix.
**Pros:** Generally the most efficient approach for the given constraints.; Significantly faster than Floyd-Warshall for sparse graphs (where P << N^2).; Provides O(1) query time after the pre-computation is complete.
**Cons:** The implementation is slightly more complex than Floyd-Warshall, as it involves graph data structures (adjacency list) and traversal logic.; Still requires O(N^2) space, which can be large.
### Explanation
Similar to the Floyd-Warshall approach, the goal is to pre-compute a data structure that allows for O(1) query time. Here, we also use a 2D matrix to store the transitive closure.

The algorithm is as follows:
1.  Build an adjacency list representation of the graph from the `prerequisites`.
2.  Create a `boolean[][] isPrerequisite` matrix to store the transitive closure.
3.  Iterate through each course `i` from `0` to `numCourses - 1`.
4.  For each `i`, perform a complete graph traversal (e.g., BFS) starting from `i`.
5.  During the traversal starting from `i`, for every node `j` that is visited, it means `j` is reachable from `i`. We record this fact by setting `isPrerequisite[i][j] = true`. The `isPrerequisite[i]` row itself can be used to track visited nodes for the traversal starting at `i`, avoiding the need for a separate `visited` array in each iteration.
6.  After iterating through all courses `i`, the `isPrerequisite` matrix will be fully populated with all reachability information.
7.  Process the queries by looking up the results in the `isPrerequisite` matrix in O(1) time.

```java
class Solution {
    public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] p : prerequisites) {
            adj.get(p[0]).add(p[1]);
        }

        boolean[][] isPrerequisite = new boolean[numCourses][numCourses];
        for (int i = 0; i < numCourses; i++) {
            // Perform BFS from each node to find all reachable nodes
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(i);
            // No need for a separate visited array, we can use the isPrerequisite[i] row
            while (!queue.isEmpty()) {
                int curr = queue.poll();
                for (int neighbor : adj.get(curr)) {
                    if (!isPrerequisite[i][neighbor]) {
                        isPrerequisite[i][neighbor] = true;
                        queue.offer(neighbor);
                    }
                }
            }
        }

        List<Boolean> ans = new ArrayList<>();
        for (int[] q : queries) {
            ans.add(isPrerequisite[q[0]][q[1]]);
        }
        return ans;
    }
}
```
### Algorithm
*   Build an adjacency list `adj` from the `prerequisites` array.
*   Initialize an `N x N` boolean matrix `isPrerequisite` to store the transitive closure, with all values initially `false`.
*   Iterate through each course `i` from `0` to `N-1`.
    *   For each `i`, perform a graph traversal (like BFS) starting from `i` to find all courses that are reachable from it.
    *   Use a queue for the BFS, starting with `i`.
    *   During the traversal, for every `neighbor` of the `current` course, if `isPrerequisite[i][neighbor]` is `false`, it means we haven't established this path yet. Set `isPrerequisite[i][neighbor] = true` and add the `neighbor` to the queue to explore its successors.
*   After iterating through all `N` starting courses, the `isPrerequisite` matrix is fully computed.
*   For each query `[u, v]`, the answer is `isPrerequisite[u][v]`, which is an O(1) lookup.
*   Collect the results and return.

# Solutions
### Java

```java
class Solution {
public
  List<Boolean> checkIfPrerequisite(int n, int[][] prerequisites,
                                    int[][] queries) {
    boolean[][] f = new boolean[n][n];
    for (var p : prerequisites) {
      f[p[0]][p[1]] = true;
    }
    for (int k = 0; k < n; ++k) {
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
          f[i][j] |= f[i][k] && f[k][j];
        }
      }
    }
    List<Boolean> ans = new ArrayList<>();
    for (var q : queries) {
      ans.add(f[q[0]][q[1]]);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<bool> checkIfPrerequisite(int n, vector<vector<int>> &prerequisites,
                                   vector<vector<int>> &queries) {
    bool f[n][n];
    memset(f, false, sizeof(f));
    for (auto &p : prerequisites) {
      f[p[0]][p[1]] = true;
    }
    for (int k = 0; k < n; ++k) {
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
          f[i][j] |= (f[i][k] && f[k][j]);
        }
      }
    }
    vector<bool> ans;
    for (auto &q : queries) {
      ans.push_back(f[q[0]][q[1]]);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def checkIfPrerequisite(self, n: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]: f = [[False] * n for _ in range(n)] for a, b in prerequisites: f[a][b] = True for k in range(n): for i in range(n): for j in range(n): if f[i][k] and f[k][j]: f[i][j] = True return [f[a][b] for a, b in queries]

```