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^51 <= edges.length <= min(10^5, n * (n - 1) / 2)edges[i].length == 20 <= fromi, toi < n(fromi, toi) are distinct.The nodes that have no incoming edges cannot be reached by any other nodes. Thus, these nodes must be included in the result set for ensuring all nodes in the graph are reachable. This is because they can naturally be start points of paths that reach out to other nodes.
We create an array to keep track of nodes with incoming edges. We iterate over all the edges, marking nodes that have incoming edges as true. Finally, we collect all nodes that are not marked as having incoming edges because these are essential to reach all other nodes.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n + m), where n is the number of nodes and m is the number of edges.
Space Complexity: O(n) for storing incoming edges information.
Minimum Number of Vertices to Reach all Nodes - Leetcode 1557 - Python • NeetCodeIO • 6,576 views views
Watch 9 more video solutions →Practice Minimum Number of Vertices to Reach All Nodes with our built-in code editor and test cases.
Practice on FleetCode