Medium

Quiz

#1462 Course Schedule IV

APPROACH

There are numCourses courses labeled 0 to numCourses - 1. The array prerequisites encodes direct dependencies: prerequisites[i] = [ai, bi] means course ai must be completed before course bi.

Prerequisite relationships are transitive — if a must precede b and b must precede c, then a must also precede c.

For each query [uj, vj] in queries, determine whether uj is a prerequisite (directly or indirectly) of vj. Return a boolean array answer where answer[j] is the result for query j.

Example 1:

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:

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

Output: [true,true]

1 of 4

1:00

What is the optimal approach for this problem?