Does This Step Come First

Medium

A recipe has n steps numbered 0 to n - 1. A pair [a, b] in steps means step a must be done before step b. The dependencies contain no cycles. A dependency can also be indirect: if a must come before b and b before c, then a must come before c as well. You also get a list questions, where questions[j] = [u, v] asks whether step u has to be done before step v, directly or through a chain. Return the answers as a list of True / False in the same order.

Example 1

n=4, steps=[[2, 0], [0, 3]], questions=[[2, 3], [3, 2], [1, 0]] → [True, False, False]

Step 2 comes before 0 and 0 comes before 3, so 2 is needed for 3 through 0. The reverse is false, and step 1 is not linked to anything.

Example 2

n=3, steps=[], questions=[[0, 1], [2, 1]] → [False, False]

There are no dependencies at all, so both answers are false.

Example 3

n=5, steps=[[4, 3], [3, 1], [1, 0], [4, 2]], questions=[[4, 0], [2, 0], [3, 4]] → [True, False, False]

Constraints

2 ≤ n ≤ 100
0 ≤ len(steps) ≤ n·(n − 1) / 2
steps[i] = [a, b], 0 ≤ a, b < n, a ≠ b, all pairs distinct
The dependencies contain no cycles
1 ≤ len(questions) ≤ 10⁵
questions[j] = [u, v], 0 ≤ u, v < n, u ≠ v

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Breadth-First Search Graph Topological Sort

Similar problems

Module Build Order Medium Course Enrollment Queue Medium Best Roots for a Tree Medium Routes That Always End Medium Longest Hike Through the Woods Medium

Input

n=4, steps=[[2, 0], [0, 3]], questions=[[2, 3], [3, 2], [1, 0]]

Expected

[True, False, False]

Run checks the first 3 tests in your browser. Submit checks all 180 tests on the server, hidden ones included.