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

Master LeetCode problem 1557 (Minimum Number of Vertices to Reach All Nodes), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1557. Minimum Number of Vertices to Reach All Nodes

Medium

Graph

Problem Explanation

Explanation

To find the minimum number of vertices to reach all nodes in a directed acyclic graph, we can identify the vertices that have no incoming edges. These vertices are guaranteed to be able to reach all other vertices in the graph. Therefore, we can simply iterate through all the edges and mark the destination vertices. Finally, we return the vertices that were not marked.

Algorithm

Initialize a set to store all vertices.
Iterate through all edges and mark the destination vertices.
Iterate through all vertices and add the ones that were not marked to the result set.
Return the result set as the answer.

Time Complexity

The time complexity of this algorithm is O(n + E), where n is the number of vertices and E is the number of edges.

Space Complexity

The space complexity of this algorithm is O(n), where n is the number of vertices.

Solution Code

import java.util.*;

class Solution {
    public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
        Set<Integer> reachable = new HashSet<>();
        for (List<Integer> edge : edges) {
            reachable.add(edge.get(1));
        }
        
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (!reachable.contains(i)) {
                result.add(i);
            }
        }
        
        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1557 (Minimum Number of Vertices to Reach All Nodes)?

This page provides optimized solutions for LeetCode problem 1557 (Minimum Number of Vertices to Reach All Nodes) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1557 (Minimum Number of Vertices to Reach All Nodes)?

The time complexity for LeetCode 1557 (Minimum Number of Vertices to Reach All Nodes) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1557 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1557 in Java, C++, or Python.

Back to LeetCode Solutions