Find the smallest set of starting vertices in a directed graph so that every node is reachable from at least one chosen vertex.
Problem
You are given a directed graph with n vertices labeled from 0 to n - 1, and a list of directed edges edges, where edges[i] = [fromi, toi] indicates a one-way edge from fromi to toi.
Return the smallest set of vertices from which all vertices in the graph are reachable.
If multiple valid answers exist, return any of them.
Key idea
A vertex only needs to be included if no edge points to it. Any vertex with at least one incoming edge can be reached from some other vertex, so it does not need to be a starting point.
Input Format
n: number of vertices, labeled0..n-1edges: list of directed edges[[from, to], ...]
Output Format
Return a list of vertices forming a minimum-size starting set such that every vertex is reachable from at least one returned vertex.
Constraints
1 <= n <= $10^{5}$0 <= edges.length <= $10^{5}$0 <= fromi, toi < n- The graph may be disconnected
- Edges are directed
Example 1
Input
n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]
Output
[0,3]
Explanation
Vertices 0 and 3 have no incoming edges. Starting from 0 reaches 1, 2, and 5; starting from 3 reaches 4 and then 2. Together they can reach every vertex.
Example 2
Input
n = 5, edges = [[0,1],[2,1],[3,1],[1,4]]
Output
[0,2,3]
Explanation
Vertex 1 and 4 have incoming edges, so they do not need to be chosen. The only vertices with no incoming edges are 0, 2, and 3.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.