Starting Points of a DAG

Medium

You get a directed graph without cycles: n nodes numbered 0 to n - 1 and a list of arrows links, where links[i] = [a, b] is an arrow from a to b. Find the smallest set of nodes from which every node of the graph can be reached by following arrows (each node in the set counts as reachable from itself). Such a set is always unique. Return its nodes in any order.

Example 1

n=5, links=[[0, 2], [1, 2], [2, 3], [2, 4]] → [0, 1]

No arrow leads into 0 or 1, so both are required, and 2, 3 and 4 are reachable from them.

Example 2

n=4, links=[[3, 0], [0, 1], [1, 2]] → [3]

Every node is reachable from 3 along the chain.

Example 3

n=3, links=[[0, 1]] → [0, 2]

Node 2 is not connected to anything, so it has to be picked on its own.

Constraints

2 ≤ n ≤ 10⁵
1 ≤ len(links) ≤ min(10⁵, n · (n - 1) / 2)
0 ≤ a, b < n, a ≠ b
All arrows are distinct
The graph has no cycles

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Graph

Similar problems

Module Build Order Medium Course Enrollment Queue Medium Do the Links Form a Tree Medium Best Roots for a Tree Medium Isolated Groups in a Network Medium

Input

n=5, links=[[0, 2], [1, 2], [2, 3], [2, 4]]

Expected

[0, 1]

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