Minimum Number of Vertices to Reach All Nodes
Medium · Graphs · Graph
Problem
You are given a directed acyclic graph with n vertices numbered 0 to n - 1, and a list edges where edges[i] = [from, to] is a directed edge from from to to.
Return the smallest set of vertices from which every vertex can be reached (a chosen vertex counts as reaching itself). This set is unique. You may list its vertices in any order.
Examples
Input: n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]] Output: [0,3]
Nothing points into 0 or 3. 0 reaches 1, 2, 5 and 3 reaches 4.
Input: n = 4, edges = [[0,1],[1,2],[2,3]] Output: [0]
Vertex 0 reaches the whole chain.
Input: n = 3, edges = [[2,1]] Output: [0,2]
Vertex 0 has no edges at all, so it must be chosen; 2 covers 1.
Constraints
- 2 <= n <= 10^5
- 1 <= edges.length <= min(10^5, n * (n - 1) / 2)
- edges[i] = [from, to] with 0 <= from, to < n
- All pairs are distinct.
- The graph has no cycles.
Approaches
- Search from every vertex — time O(n · (n + E)), space O(n + E)
Follow-up
If the graph may have cycles, a cycle with no edge coming in from outside needs one of its vertices chosen. Collapse each strongly connected component into one vertex and count the components with in-degree 0.
Related problems
Start free on Cariara · Coding problems · System design studio
