Minimum Number of Vertices to Reach All Nodes

Given a directed acyclic graph, return the minimum set of starting vertices needed so every node is reachable from at least one chosen vertex. Pattern focus: Degree. The answer is the set of nodes with indegree 0.

Input Format

n = number of nodes, edges = directed edges

Output Format

array of starting vertices with indegree 0

Constraints

  • 1 <= input size <= 10^5
  • -10^9 <= numeric values <= 10^9
  • n, edges must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

n = 6
edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]

Output:

[0,3]

Explanation:

Nodes 0 and 3 have indegree 0.

Example 2:

Input:

n = 3
edges = [[0,1],[0,2]]

Output:

[0]

Explanation:

Only node 0 has indegree 0.

Loading...
Minimum Number of Vertices to Reach All Nodes