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.
The nodes that have no incoming edges cannot be reached by any other nodes. Thus, these nodes must be included in the result set for ensuring all nodes in the graph are reachable. This is because they can naturally be start points of paths that reach out to other nodes.
We create an array to keep track of nodes with incoming edges. We iterate over all the edges, marking nodes that have incoming edges as true. Finally, we collect all nodes that are not marked as having incoming edges because these are essential to reach all other nodes.
Time Complexity: O(n + m), where n is the number of nodes and m is the number of edges.
Space Complexity: O(n) for storing incoming edges information.
| Approach | Complexity |
|---|---|
| Find Nodes with No Incoming Edges | Time Complexity: O(n + m), where n is the number of nodes and m is the number of edges. |
| Default Approach | — |
| 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 |
Minimum Number of Vertices to Reach all Nodes - Leetcode 1557 - Python • NeetCodeIO • 7,768 views views
Watch 9 more video solutions →Practice Minimum Number of Vertices to Reach All Nodes with our built-in code editor and test cases.
Practice on FleetCode