Minimum Number of Vertices to Reach All Nodes

Minimum Number of Vertices to Reach All Nodes

1. What is this problem about?

You are given a Directed Acyclic Graph (DAG) with n vertices. Your goal is to find the smallest set of vertices from which all other nodes in the graph are reachable. You need to return the list of these vertices. Because it's a DAG, the solution is simpler than it might first appear in a general graph.

2. Why is this asked in interviews?

Companies like Microsoft and Airbnb ask this to test basic graph theory knowledge, specifically the concept of "in-degree." It's a "knowledge-check" problem—can the candidate recognize that in a DAG, any node that has no incoming edges must be included in the starting set, and any node that does have an incoming edge is reachable from somewhere else?

3. Algorithmic pattern used

The algorithmic pattern is Graph Traversal (In-degree counting). In any DAG, a node is reachable from another node if there's a path. The "source" nodes (those with no incoming edges) are the only nodes that cannot be reached from any other node. Therefore, the minimum set of vertices to reach all nodes is simply the set of all nodes with an in-degree of zero.

4. Example explanation

Consider edges: [[0,1], [0,2], [2,5], [3,4], [4,2]].

• In-degree of 0: 0 (no one points to 0)
• In-degree of 1: 1 (0 points to 1)
• In-degree of 2: 2 (0 and 4 point to 2)
• In-degree of 3: 0 (no one points to 3)
• In-degree of 4: 1 (3 points to 4)
• In-degree of 5: 1 (2 points to 5) Nodes with 0 in-degree: [0, 3]. From 0, you reach 1, 2, 5. From 3, you reach 4 (and then 2, 5). Total coverage.

5. Common mistakes candidates make

The most common mistake is over-engineering the solution using Depth-First Search (DFS) or Breadth-First Search (BFS) for every node. While DFS/BFS can solve it, they are significantly slower and more complex than simply counting in-degrees. Another mistake is forgetting that the problem specifically mentions a Directed Acyclic Graph, which is why the in-degree logic works so cleanly.

6. Interview preparation tip

Always check if a graph is a DAG. DAGs have unique properties (like the existence of source and sink nodes and topological sorting) that often allow for linear-time solutions to reachability and pathfinding problems.