1557. Minimum Number of Vertices to Reach All Nodes LeetCode Solution

In this guide, you will get 1557. Minimum Number of Vertices to Reach All Nodes LeetCode Solution with the best time and space complexity. The solution to Minimum Number of Vertices to Reach All Nodes problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Minimum Number of Vertices to Reach All Nodes solution in C++
4. Minimum Number of Vertices to Reach All Nodes solution in Java
5. Minimum Number of Vertices to Reach All Nodes solution in Python
6. Additional Resources

Problem Statement of 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.

Complexity Analysis

• Time Complexity: O(|E|)
• Space Complexity: O(n)

1557. Minimum Number of Vertices to Reach All Nodes LeetCode Solution in C++

class Solution {
 public:
  vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) {
    vector<int> ans;
    vector<int> inDegrees(n);

    for (const vector<int>& edge : edges)
      ++inDegrees[edge[1]];

    for (int i = 0; i < inDegrees.size(); ++i)
      if (inDegrees[i] == 0)
        ans.push_back(i);

    return ans;
  }
};
/* code provided by PROGIEZ */

1557. Minimum Number of Vertices to Reach All Nodes LeetCode Solution in Java

class Solution {
  public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
    List<Integer> ans = new ArrayList<>();
    int[] inDegrees = new int[n];

    for (List<Integer> edge : edges)
      ++inDegrees[edge.get(1)];

    for (int i = 0; i < inDegrees.length; ++i)
      if (inDegrees[i] == 0)
        ans.add(i);

    return ans;
  }
}
// code provided by PROGIEZ

1557. Minimum Number of Vertices to Reach All Nodes LeetCode Solution in Python

class Solution:
  def findSmallestSetOfVertices(
      self,
      n: int,
      edges: list[list[int]],
  ) -> list[int]:
    inDegrees = [0] * n

    for _, v in edges:
      inDegrees[v] += 1

    return [i for i, d in enumerate(inDegrees) if d == 0]
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.