Course Schedule IV

Explanation & Solution

Description

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 course ai must be taken before course bi.

Prerequisites can 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 each query, answer whether course uj is a prerequisite of course vj (either directly or indirectly).

Return a boolean array answer where answer[j] is the answer to the j-th query.

Input: numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]

Output:[false,true]

false

true

Explanation: Course 1 is a prerequisite of course 0. Course 0 is not a prerequisite of course 1.

Constraints

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

Approach

Topological Sort pattern

1. Build the Graph

Create an adjacency list from the prerequisites array
For each pair [a, b], add a directed edge from a to b (a is prerequisite of b)
Track the in-degree of each node for topological sorting

2. Initialize Reachability Sets

Create a Set for each course to store all its prerequisites (direct and indirect)
Initially all sets are empty

3. Topological Sort with Reachability Propagation

Use Kahn's algorithm — start BFS from nodes with in-degree 0
When processing an edge curr -> next:
Add curr to reachable[next] (direct prerequisite)
Add all of reachable[curr] to reachable[next] (indirect prerequisites)
Decrement in-degree and add to queue when it reaches 0
Processing in topological order ensures that when we visit a node, all its prerequisites are already computed

4. Answer Queries

For each query [u, v], check if u is in reachable[v]
If yes, u is a prerequisite (direct or indirect) of v
Return the boolean array of answers

Key Insight

Processing nodes in topological order guarantees that when we propagate reachability from curr to next, curr's reachability set is already complete
This is essentially computing the transitive closure of the prerequisite graph
Using Sets makes the lookup for each query O(1)

Time

O(V^2 + V*E + Q) where V is numCourses, E is prerequisites, and Q is queries

Space

O(V^2) for the reachability sets in the worst case

Solution Code

Find Eventual Safe States