 All Problems
Minimum Number of Vertices to Reach All Nodes
medium
topological sort
graph
amazon
google
facebook

Given a directed acyclic graph with n vertices (0 to n-1) and a list of edges, find the smallest set of vertices from which all nodes are reachable.

Example 1:

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

Example 2:

Input: n=5, edges=[[0,1],[2,1],[3,1],[1,4],[2,4]]
Output: [0,2,3]

Constraints:

  • 2 <= n <= 10^5
  • edges[i].length == 2
  • The graph is a DAG.
Run to check your code against the sample cases, or submit to run every case