hardGraphsPure DSA~25 min
Smallest Set of Entry Nodes Reaching the Whole DAG
From which minimal set of entry services can a message, by following directed dependencies, eventually reach every service in a DAG?
Problem
Given a directed acyclic graph of n nodes (0..n-1) and its directed edges, return the smallest set of vertices from which all nodes in the graph are reachable. It is guaranteed a unique minimal solution exists.
Input
An integer n and an edges list of directed [from, to] pairs.
Output
A list of the entry vertices (any order).
Constraints
- 2 <= n <= 10^5
- 1 <= edges.length <= min(2*10^5, n*(n-1)/2)
- The graph is a DAG.
Examples
Example 1
Input
n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]
Output
[0,3]
Nodes 0 and 3 (the only ones with no incoming edges) reach everything.
Example 2
Input
n = 5, edges = [[0,1],[2,1],[3,1],[1,4],[2,4]]
Output
[0,2,3]
The three nodes with no in-edges form the answer.