{x}
blog image

Minimum Number of Vertices to Reach All Nodes

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^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.

Solution Explanation

This problem asks to find the minimum set of vertices in a directed acyclic graph (DAG) such that all nodes in the graph are reachable from these vertices. The solution leverages the fact that a vertex that is a destination of an edge (incoming edge) does not need to be in the minimum set because it's reachable from its predecessors. Therefore, only vertices with no incoming edges are considered.

Approach

The core idea is to count the number of incoming edges for each vertex. If a vertex has zero incoming edges, it must be included in the minimum set because it cannot be reached from any other vertex. Vertices with incoming edges can be reached from other vertices, so they don't need to be explicitly included in the result.

Algorithm

  1. Initialization: Create an array cnt of size n (number of vertices) initialized to 0. This array will store the count of incoming edges for each vertex.

  2. Count Incoming Edges: Iterate through the edges list. For each edge [from, to], increment the count of incoming edges for vertex to ( cnt[to]++).

  3. Identify Source Vertices: Iterate through the cnt array. If cnt[i] is 0, it means vertex i has no incoming edges, so add it to the result list ans.

  4. Return Result: Return the ans list containing the vertices with no incoming edges.

Time and Space Complexity

  • Time Complexity: O(N + E), where N is the number of vertices and E is the number of edges. The algorithm iterates through the edges once (O(E)) and then iterates through the vertices once (O(N)).

  • Space Complexity: O(N). The cnt array requires O(N) space to store the incoming edge counts for each vertex. The ans list also requires at most O(N) space in the worst case.

Code Explanation (Python)

from collections import Counter
 
class Solution:
    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:
        cnt = Counter(t for _, t in edges) #Efficient way to count incoming edges using Counter
        return [i for i in range(n) if cnt[i] == 0] #List comprehension for concise code

The Python solution utilizes the Counter object from the collections module for efficient counting of incoming edges. This eliminates the need for manual iteration and makes the code more readable and potentially faster. The list comprehension elegantly filters and creates the result list.

Other languages follow a similar logic, but the specific syntax and data structures might vary slightly. The core algorithm remains consistent across all languages.