Watch 10 video solutions for Minimum Number of Vertices to Reach All Nodes, a medium level problem involving Graph. This walkthrough by NeetCodeIO has 7,768 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given a directed acyclic graph, with n vertices numbered from 0 to n-1, and an array edges where edges[i] = [fromi, toi] represents a directed edge from node fromi to node toi.
Find the smallest set of vertices from which all nodes in the graph are reachable. It's guaranteed that a unique solution exists.
Notice that you can return the vertices in any order.
Example 1:
Input: n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]] Output: [0,3] Explanation: It's not possible to reach all the nodes from a single vertex. From 0 we can reach [0,1,2,5]. From 3 we can reach [3,4,2,5]. So we output [0,3].
Example 2:
Input: n = 5, edges = [[0,1],[2,1],[3,1],[1,4],[2,4]] Output: [0,2,3] Explanation: Notice that vertices 0, 3 and 2 are not reachable from any other node, so we must include them. Also any of these vertices can reach nodes 1 and 4.
Constraints:
2 <= n <= 10^51 <= edges.length <= min(10^5, n * (n - 1) / 2)edges[i].length == 20 <= fromi, toi < n(fromi, toi) are distinct.Problem Overview: You are given a directed graph with n nodes labeled from 0 to n-1 and a list of directed edges. The task is to return the minimum set of starting vertices such that every node in the graph is reachable from at least one of them.
Approach 1: Graph Traversal from Every Node (Brute Force) (Time: O(V * (V + E)), Space: O(V + E))
A straightforward approach is to treat every node as a potential starting vertex. Build an adjacency list and run a traversal such as DFS or BFS from each node to mark which vertices it can reach. Track coverage of all nodes and determine the minimal set of sources required. This works but becomes expensive because each traversal scans the graph again, leading to O(V * (V + E)) time in dense cases. It demonstrates understanding of graph traversal, but it is unnecessary for this specific problem.
Approach 2: Find Nodes with No Incoming Edges (Optimal) (Time: O(V + E), Space: O(V))
The key observation: if a node has at least one incoming edge, it can already be reached from another node. Only nodes with zero indegree cannot be reached by anyone else, so they must be included in the starting set. Iterate through the edge list and compute the indegree of each vertex. After processing all edges, scan the indegree array and collect every node with value 0. These nodes form the smallest set of vertices needed to reach the entire graph.
This works because any node with incoming edges will eventually be reachable from one of the zero‑indegree nodes in a directed acyclic structure of dependencies. The idea is closely related to the starting step of topological sorting, where nodes with zero indegree represent valid starting points.
The algorithm performs a single pass through the edges to compute indegrees and another pass through the vertices to collect answers. That results in linear complexity relative to the graph size. Memory usage stays small since only an integer array of size V is needed.
Recommended for interviews: Interviewers expect the indegree observation. Brute force traversal shows you understand graph reachability, but the optimal approach shows you recognize structural properties of directed graphs and can reduce the problem to a simple indegree scan in O(V + E) time.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Graph Traversal from Every Node | O(V * (V + E)) | O(V + E) | Conceptual understanding of reachability using DFS/BFS |
| Nodes with No Incoming Edges (Indegree) | O(V + E) | O(V) | Optimal solution for directed graphs where starting sources must be identified |