hardGraphsPure DSA~35 min
Answer Whether One Stage Is a Prerequisite of Another
Given direct prerequisite relations between build stages, answer many queries of the form 'is stage u a (possibly indirect) prerequisite of stage v?'
Problem
There are numCourses courses (0..numCourses-1) with prerequisites where prerequisites[i] = [a, b] means a must be taken before b. For each query [u, v], return true if u is a prerequisite of v (directly or transitively). Return a boolean list aligned with queries.
Input
An integer numCourses, a prerequisites list, and a queries list of [u, v].
Output
A list of booleans, one per query.
Constraints
- 2 <= numCourses <= 100
- 0 <= prerequisites.length <= n*(n-1)/2
- The prerequisite graph is a DAG.
Examples
Example 1
Input
numCourses = 3, prerequisites = [[0,1],[1,2]], queries = [[0,2],[2,0]]
Output
[true,false]
0 -> 1 -> 2 makes 0 a prerequisite of 2, but not vice versa.
Example 2
Input
numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]]
Output
[false,false]
With no prerequisites, neither reaches the other.