1050MediumDepth-First SearchBreadth-First SearchGraph TheoryTopological Sort

Which Modules Must Come First

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a 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)

The intended approach

Time O(c^3 + q) for c modules and q questions.Space O(c^2) for the table.

There may be far more questions than modules, so work out every forerunner relation once and then answer each question by looking it up. Start from a table marking the requirements exactly as given. Then take each module in turn as a stepping stone: whenever some module reaches the stone and the stone reaches another, mark that the first reaches the second. Sweeping every module as a stone, in any order, settles every chain. To see why, take any chain and the highest-numbered module strictly inside it: by the time that module is used as the stone, the two halves either side of it have already been marked, so the whole chain is caught then. That is the modules cubed for the table, a hundred cubed at the largest, and then a single lookup per question.

Pythonentry point: check_if_prerequisite

def check_if_prerequisite(count, before, asks):
    reach = [[False] * count for _ in range(count)]
    for pair in before:
        reach[pair[0]][pair[1]] = True
    for mid in range(count):
        stone = reach[mid]
        for a in range(count):
            if not reach[a][mid]:
                continue
            row = reach[a]
            for b in range(count):
                if stone[b]:
                    row[b] = True
    out = []
    for pair in asks:
        out.append(reach[pair[0]][pair[1]])
    return out

The obvious version

Answer each question on its own by walking outward from the module asked about, following the requirements forward with a queue until the other module turns up or nothing new is left to reach. Costs a walk per question rather than one table settled up front.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_check_if_prerequisite(count, before, asks):
    from collections import deque
    after = [[] for _ in range(count)]
    for pair in before:
        after[pair[0]].append(pair[1])
    out = []
    for pair in asks:
        start = pair[0]
        target = pair[1]
        seen = [False] * count
        seen[start] = True
        queue = deque([start])
        found = False
        while queue:
            here = queue.popleft()
            for there in after[here]:
                if there == target:
                    found = True
                    break
                if not seen[there]:
                    seen[there] = True
                    queue.append(there)
            if found:
                break
        out.append(found)
    return out

How this problem was checked

Reference solution executed against 14 test cases — 14 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in