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

The problem

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.

Example

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

Python solution

class Solution:
    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:
        cnt = Counter(t for _, t in edges)
        return [i for i in range(n) if cnt[i] == 0]

Complexity

Pattern: Depth-First Search

Follow one path to its end before trying the next — the default way to explore a graph. LeetCode 1557. Minimum Number of Vertices to Reach All Nodes is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Graph.

The depth-first search guide has the Python template for the pattern and the 366 LeetCode problems that use it.

Related problems