1557. Minimum Number of Vertices to Reach All Nodes

MediumGraph
Leetcode Link

Problem Description

The given problem presents a Directed Acyclic Graph (DAG) which means a graph that has directed edges and no cycles. It includes 'n' vertices which are labeled from 0 to n-1. We're also provided an array of edges where each edge is represented by a pair [from_i, to_i], indicating a directed edge that goes from vertex from_i to vertex to_i.

The task is to find the smallest set of vertices with the property that starting from those vertices, one can reach all other vertices in the graph. The important aspect of this problem is to understand that these vertices should be the starting points for traversing the entire graph. It is also given that there is a unique solution for this problem, which means there's only one smallest set of such vertices and the vertices can be returned in any sequence.

Intuition

To solve this problem, we take advantage of a key characteristic of DAGs — a node that has no incoming edges can be a starting point to reach all other nodes because there are no other nodes that need to be visited before it. Conversely, nodes with incoming edges have at least one other node that must be processed first.

The solution approach is as follows:

  1. We initialize a counter cnt to keep track of the number of incoming edges each vertex has.
  2. To fill this counter, we iterate over all directed edges. For each edge, we increase the count for the target vertex to_i because this edge represents an incoming edge to to_i.
  3. Once we have the count of incoming edges for each vertex, the vertices with a count of zero are exactly the vertices we're looking for. They have no incoming edges and can serve as starting points.
  4. We iterate through all vertices from 0 to n-1, and those with a cnt value of zero are added to our results list as they represent the smallest set of vertices that can be used to reach all other vertices in the graph.

By following this process, we efficiently identify the vertices that are not dependent on any other vertices to be visited first, which fulfills the requirement of reaching every vertex in the graph starting from the smallest set of initial vertices.

Learn more about Graph patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

Solution Approach

The solution is implemented in Python, and it uses the Counter class from the collections module to keep track of the number of incoming edges for each vertex in the graph.

Here's a step-by-step breakdown of the algorithm implemented in the solution code:

  1. A Counter object named cnt is created to count the incoming edges of each vertex. This is constructed by iterating over the edges list and counting each target vertex t (the second element of each edge [_, t]).

  2. A for-loop comprehensions construct:

    1[i for i in range(n) if cnt[i] == 0]

    This is used to iterate over all vertex indices from 0 to n-1.

  3. For each index i, the loop checks if cnt[i] == 0. This condition is true for the vertices that do not have any incoming edges (meaning they are not the target of any edge in the edges list).

  4. The indices i that satisfy the condition are collected into a list. These form the smallest set of vertices from which all nodes in the graph are reachable.

  5. The final list is returned as the output of the findSmallestSetOfVertices function.

The algorithm essentially uses a counting method to identify source nodes in the graph. A source node is a node with no incoming edges, which means that it can be a starting point, and you can reach every other node in the DAG via a path from these sources.

This algorithm runs in linear time relative to the number of edges, as it only makes a single pass through the edges list to build the counter and then another pass through the list of vertex indices to collect the result. Therefore, the time complexity is O(E + V), where E is the number of edges and V is the number of vertices.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Example Walkthrough

Let's illustrate the solution approach with a small example:

Suppose we have a graph with n = 4 vertices and the following directed edges: edges = [[0,1], [0,2], [1,3], [2,3]]. The edges indicate that there are directed paths from vertex 0 to vertex 1, from vertex 0 to vertex 2, from vertex 1 to vertex 3, and from vertex 2 to vertex 3.

Let's walk through the approach:

  1. We set up a counter cnt to track the incoming edges to each vertex. In our graph representation, the incoming edges are described by the second element in each edge pair. So initially, the counter cnt for all vertices is set to zero: cnt = {0: 0, 1: 0, 2: 0, 3: 0}.

  2. Next, we iterate over the list of edges to update these counts. After iterating, we get:

    • For edge [0,1], increase cnt[1] by 1;
    • For edge [0,2], increase cnt[2] by 1;
    • For edge [1,3], increase cnt[3] by 1;
    • For edge [2,3], increase cnt[3] by 1 again.

    After processing all edges, the updated counts of incoming edges for the vertices are: cnt = {0: 0, 1: 1, 2: 1, 3: 2}.

  3. With these counts, we now identify vertices with zero incoming edges, as they are potential starting points to reach any other vertex. From cnt, we see that only vertex 0 has a count of zero.

  4. Using a list comprehension, we extract vertices with zero counts into our result list:

    1result = [i for i in range(n) if cnt[i] == 0] # result will be [0]

  5. The final result list, which contains the smallest set of vertices from which all other vertices are reachable, is [0].

This is the end of the example walkthrough. By starting at vertex 0, we can reach all other vertices in the graph, fulfilling the task. The solution approach works efficiently, regardless of the graph's size, by focusing on finding vertices with no dependencies (no incoming edges).

Solution Implementation

1from collections import Counter
2from typing import List
3
4class Solution:
5    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:
6        # Create a counter to count how many times each node is the target of an edge
7        target_counter = Counter(target for _, target in edges)
8      
9        # Systematically check each vertex from 0 to n-1
10        # If the count of incoming edges is 0, then it is not a target of any edge
11        # and must be included in the smallest set of vertices that reaches all nodes
12        return [vertex for vertex in range(n) if target_counter[vertex] == 0]
13
1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
5    public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
6        // Create an array to count the in-degree of each vertex
7        int[] inDegreeCount = new int[n];
8      
9        // Iterate over the edges to count the in-degree for each vertex
10        for (List<Integer> edge : edges) {
11            // Increment the in-degree count of the destination vertex
12            inDegreeCount[edge.get(1)]++;
13        }
14      
15        // Prepare a list to hold the answer vertices
16        List<Integer> answerVertices = new ArrayList<>();
17      
18        // Go through the vertices
19        for (int i = 0; i < n; i++) {
20            // If a vertex has an in-degree of 0, it's not reachable from any other vertex
21            if (inDegreeCount[i] == 0) {
22                // Add the vertex to answerVertices as it is a candidate for the
23                // smallest set of vertices from which all nodes are reachable
24                answerVertices.add(i);
25            }
26        }
27      
28        // Return the list of vertices from which all other nodes are reachable
29        return answerVertices;
30    }
31}
32
1class Solution {
2public:
3    // This method finds the smallest set of vertices from which all nodes are reachable
4    // in the given directed graph represented by 'n' nodes and 'edges'.
5    vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) {
6        // Initialize a counter vector to track the incoming edges for each vertex.
7        vector<int> incomingEdgesCounter(n, 0);
8
9        // Iterate over all edges to increment the counter of the destination nodes.
10        for (const auto& edge : edges) {
11            ++incomingEdgesCounter[edge[1]]; // Increment the counter of incoming edges for the destination node.
12        }
13      
14        // Prepare an vector to store the answer.
15        vector<int> answer;
16
17        // Iterate over all nodes to check which nodes have zero incoming edges.
18        for (int i = 0; i < n; ++i) {
19            // If the current node has zero incoming edges,
20            // it means it cannot be reached by other nodes,
21            // so we add it to the answer set.
22            if (incomingEdgesCounter[i] == 0) {
23                answer.push_back(i);
24            }
25        }
26
27        // Return the vector containing all nodes with zero incoming edges.
28        return answer;
29    }
30};
31
1/**
2 * Finds the smallest set of vertices from which all nodes in the graph are reachable.
3 * @param {number} numVertices - The total number of vertices in the graph.
4 * @param {number[][]} edges - The edges of the graph represented as an array of tuples [from, to].
5 * @returns {number[]} The array of vertex indices that form a smallest set of vertices.
6 */
7function findSmallestSetOfVertices(numVertices: number, edges: number[][]): number[] {
8    // Initialize an array to count the in-degree of each vertex.
9    const inDegreeCount: number[] = new Array(numVertices).fill(0);
10  
11    // Iterate over edges to calculate the in-degree for each vertex.
12    for (const [_, to] of edges) {
13        inDegreeCount[to]++;
14    }
15  
16    // Initialize an array to store the answer.
17    const answer: number[] = [];
18  
19    // Iterate over the vertices.
20    for (let i = 0; i < numVertices; ++i) {
21        // If the in-degree of a vertex is 0, it means that it is not reachable from any other vertex.
22        // Therefore, it must be included in the set.
23        if (inDegreeCount[i] === 0) {
24            answer.push(i);
25        }
26    }
27  
28    // Return the list of vertices that must be included in the smallest set.
29    return answer;
30}
31
Not Sure What to Study? Take the 2-min Quiz：

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Time and Space Complexity

Time Complexity

The time complexity of the given code is determined by two main operations. The first operation is the creation of the Counter, which involves iterating over all the edges. If m represents the number of edges, then this operation is O(m).

The second operation is the list comprehension, which checks each vertex to see if it has a count of zero in the Counter. Since there are n vertices, this operation is O(n).

Since these two operations happen sequentially and not nested, the overall time complexity is O(m + n).

Space Complexity

The space complexity is primarily impacted by the Counter that stores occurrence counts for the target vertices of each edge. In the worst case, all m edges might be pointing to different target vertices, so the Counter would store m key-value pairs.

Therefore, the space complexity is O(m) for the Counter. However, the output list's size is at most n in the case when no vertices are targets. This n sized list is separate from the Counter storage.

Thus, when considering both the Counter and the final output list, the space complexity is O(m + n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

How does merge sort divide the problem into subproblems?

Recommended Readings

Graph Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫