Show problems as
Classic problem #1462MediumDepth-First SearchBreadth-First SearchGraph TheoryTopological Sort

Course Schedule IV

Real-world version: Which Modules Must Come First
Tracked in this browser only
Read Course Schedule IV on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstGraph Coloring · Graphs, animated step by step

A course has count modules numbered 0 through count - 1. Each entry before[i] = [a, b] says module a has to be taken before module b. A module x is a forerunner of a module y when some chain of those requirements leads from x to y.

Each entry asks[i] = [u, v] is a question: is u a forerunner of v?

Return the answers in the order the questions are asked. The requirements never lead round in a circle.

Examples

Example 1

Input
count = 3, before = [[0, 1], [1, 2]], asks = [[0, 2], [2, 0], [1, 0]]
Output
[true, false, false]

Module 0 comes before 1 and 1 before 2, so the chain makes 0 a forerunner of 2. Neither of the other two questions runs the right way along the chain.

Example 2

Input
count = 2, before = [], asks = [[0, 1], [1, 0]]
Output
[false, false]

There are no requirements at all, so no module is a forerunner of any other.

Example 3

Input
count = 5, before = [[0, 1], [0, 2], [1, 3], [2, 3]], asks = [[0, 3], [1, 2], [3, 4]]
Output
[true, false, false]

Module 0 reaches 3 through either 1 or 2. Modules 1 and 2 sit side by side with no chain between them, and no requirement touches module 4 at all.

Constraints

  • 2 <= count <= 100
  • 0 <= before.length <= 4950
  • before[i].length == 2
  • 0 <= before[i][j] <= count - 1
  • The two modules of a requirement are different.
  • No requirement is listed twice.
  • The requirements never lead round in a circle.
  • 1 <= asks.length <= 10^4
  • 0 <= asks[i][j] <= count - 1

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def check_if_prerequisite(count: int, before: list[list[int]], asks: list[list[int]]) -> list[bool]:
Java
public List<Boolean> checkIfPrerequisite(int count, int[][] before, int[][] asks)

More on the same topics