Minimum Number of Vertices to Reach All Nodes

Problem Description

Given a directed acyclic graph, with n vertices numbered from 0 to n-1, and an array edges where edges[i] = [from_i, to_i] represents a directed edge from node from_i to node to_i. 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.

Key Insights

• A directed acyclic graph (DAG) does not have cycles, which simplifies the problem of reachability.
• A vertex that has no incoming edges cannot be reached from any other vertex, making it essential for reaching all nodes.
• The solution requires identifying all vertices that are not pointed to by any other vertex.

Space and Time Complexity

Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges. Space Complexity: O(V), for storing the incoming edge counts.

Solution

To solve the problem, we can use an array to keep track of the number of incoming edges for each vertex. The main steps are as follows:

1. Initialize an array in_degree of size n, where in_degree[i] counts the number of edges directed towards vertex i.
2. Iterate through the edges and populate the in_degree array.
3. Collect all vertices with an incoming degree of 0, as these are the starting points needed to reach all other nodes in the graph.

This approach ensures that we only traverse the graph a minimal number of times, leading to efficient identification of the required vertices.

Code Solutions