DSA problem
Course Schedule IV
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] = [a, b] indicates that you must take course a first if you want to take course b. 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 also a prerequisite of course c.
You are also given an array queries where queries[j] = [u, v]. For the j-th query, you should answer whether course u is a prerequisite of course v (directly or transitively). Return a boolean array answer, where answer[j] is the answer to the j-th query.
Because there can be many queries, the smart move is to precompute the full transitive closure once, then answer each query in O(1). Two clean ways to do that:
The first is Floyd-Warshall transitive closure. Create a boolean matrix reach[u][v] initialized from the direct edges, then for every intermediate k propagate reach[u][v] |= reach[u][k] && reach[k][v]. This runs in O(n^3) time and O(n^2) space, which is fine when n is small (≤ 100 here).
The second is a topological-order DP: process nodes in reverse topological order so that when we visit u, all its successors are already finalized; then reach[u] is the union of reach[c] over every direct successor c, with c itself added. Both methods give the same O(n^2) look-up table; each query is answered with a single reach[u][v] lookup.
Examples
numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]][false,true]numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]][false,false]numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]][true,true]Constraints
- 2 <= numCourses <= 100
- 0 <= prerequisites.length <= (numCourses * (numCourses - 1)) / 2
- prerequisites[i].length == 2
- 0 <= a, b <= numCourses - 1, a != b
- All the pairs [a, b] are unique. The prerequisites graph has no cycles.
- 1 <= queries.length <= 10^4
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.