All Prerequisite Tasks

Medium

A project has count tasks numbered from 0 to count - 1. The list deps holds the direct dependencies: a pair [a, b] means task a must be done before task b. There are no circular dependencies. Task a is a prerequisite of task b if you can get from a to b by following one or more dependencies. Return a list answer where answer[i] holds the numbers of all prerequisites of task i in increasing order.

Example 1

count=5, deps=[[0, 2], [1, 2], [2, 4], [3, 4]] → [[], [], [0, 1], [], [0, 1, 2, 3]]

Task 2 needs tasks 0 and 1. Task 4 needs 2 and 3 directly, plus 0 and 1 through task 2. Tasks 0, 1 and 3 have no prerequisites.

Example 2

count=4, deps=[[3, 2], [2, 1], [1, 0]] → [[1, 2, 3], [2, 3], [3], []]

A chain 3 → 2 → 1 → 0: task 0 needs all the others and task 3 needs none.

Example 3

count=3, deps=[] → [[], [], []]

Constraints

1 ≤ count ≤ 1000
0 ≤ len(deps) ≤ min(2000, count·(count − 1) / 2)
deps[i] = [a, b] with 0 ≤ a, b ≤ count − 1 and a ≠ b
deps has no repeated pairs
The dependencies contain no cycles

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

count=5, deps=[[0, 2], [1, 2], [2, 4], [3, 4]]

Expected

[[], [], [0, 1], [], [0, 1, 2, 3]]

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