Minimum Number of Vertices to Reach All Nodes

Problem Statement

In the context of a directed acyclic graph (DAG) where you have a defined number of vertices, n, each uniquely identified by numerical indices from 0 to n-1, and a series of directed edges connecting these vertices represented in the format edges[i] = [fromi, toi], you are tasked with determining the smallest subset of these vertices. This subset should have the distinctive quality that starting from any vertex within the subset, every other vertex in the graph can be reached. Such a subset is essential as it encompasses the crucial starting points for traversing the entire graph. The problem stipulates that a unique solution exists, ensuring that there's only one smallest subset from which all nodes are reachable. The solution does not require the vertices to be returned in a specific order, giving some flexibility in how the result is presented.

Examples

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^5
• 1 <= edges.length <= min(10^5, n * (n - 1) / 2)
• edges[i].length == 2
• 0 <= fromi, toi < n
• All pairs (fromi, toi) are distinct.

Approach and Intuition

To find the smallest set of vertices from which all nodes in the graph are reachable, we can leverage the properties of DAGs and the concept of in-degrees. An in-degree of a vertex in a directed graph is the number of incoming edges it has.

1. Understanding Reachability: We need to find a group of starting vertices such that any other vertex in the DAG can be reached. This leads us to consider vertices with zero in-degrees because:

   • If a vertex has an in-degree of zero, it cannot be reached from any other vertex in the graph, making it a critical starting point.
   • Conversely, if a vertex has a non-zero in-degree, there is at least one other vertex from which it can be reached.

2. Algorithm Design: Based on the above intuition, the steps to find the solution are:

   1. Initialize: Start by setting up an array or a similar structure to track the in-degrees of all vertices.
   2. Fill In-Degree Array: Traverse the list of edges and increment the in-degree count for the destination vertex (toi) of each edge.
   3. Identify Zero In-degree Vertices: Go through the in-degree array and add vertices with zero in-degree to the result list. These vertices are crucial as from them all other vertices can be reached either directly or indirectly.

3. Time Complexity Considerations: This approach efficiently uses the DAG's properties and operates in linear time concerning the number of vertices and edges, typically denoted as O(V + E) where V is the number of vertices and E is the number of edges. This efficiency is crucial given the constraints that allow for a high volume of nodes and edges.

In summary, the solution revolves around identifying vertices from which traversal begins and ensuring the entire graph can be explored from these starting points. By using the in-degree method, we effectively pinpoint these essential vertices with simplicity and effectiveness.

Solutions

class Solution {
public:
    vector<int> getMinimumInitialVertices(int totalNodes, vector<vector<int>>& links) {
        // Array to note vertices that are accessible via other vertices
        vector<bool> hasIncoming(totalNodes, false);
        for (vector<int>& link : links) {
            hasIncoming[link[1]] = true;
        }

        vector<int> result;
        for (int idx = 0; idx < totalNodes; idx++) {
            // Collects all vertices without any incoming edges
            if (!hasIncoming[idx]) {
                result.push_back(idx);
            }
        }

        return result;
    }
};

class Solution {
  public List<Integer> findMinimumVertices(int totalNodes, List<List<Integer>> connections) {
    // Array to track vertices with at least one incoming edge
    boolean[] hasIncoming = new boolean[totalNodes];
    for (List<Integer> connection : connections) {
      hasIncoming[connection.get(1)] = true;
    }

    List<Integer> resultVertices = new ArrayList<>();
    for (int idx = 0; idx < totalNodes; idx++) {
      // Add all nodes with no incoming edges to the result
      if (!hasIncoming[idx]) {
        resultVertices.add(idx);
      }
    }

    return resultVertices;
  }
}