< Back





1557. Minimum Number of Vertices to Reach All Nodes

Given a directed acyclic graph (DAG), we're asked to find the minimum set of vertices from which all
nodes in the graph are reachable. We can do this by finding all nodes that have no incoming edges.

The solution is as follows:


  class Solution:
      def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:
          indegrees = [0] * n
          for _, y in edges:
              indegrees[y] += 1

          return [i for i, indegree in enumerate(indegrees) if indegree == 0]


_ Time Complexity:

  O(m) - We iterate through the edges to count the indegrees.

_ Space Complexity:

  O(n) - We track the indegrees of each node.