⚡Flashcard Drill➔
NeetCode #594LC-1557MediumGraphs
← Back to All Problems

#594 · #1557 · Minimum Number of Vertices to Reach All Nodes(可以到达所有点的最少点数目)

📌 Problem Statement & Constraints

Given a DAG with n vertices and edges, return the smallest set of vertices from which all other vertices are reachable. Constraints: 2 <= n <= 10^5, 1 <= edges.length <= min(10^5, n * (n - 1) / 2), all edges are distinct.

💡 Core Algorithmic Approaches

  1. A vertex must be in the answer if no edge enters it -- nothing can reach it otherwise.
  2. Conversely, every vertex with a positive in-degree is reachable from some such source (since the graph is a DAG).
  3. So the answer is exactly the set of vertices with in-degree 0.
  4. The ordering of the result does not matter.

💻 Benchmark Python3 Implementation

class Solution:
    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:
        indeg = [0] * n
        for _, v in edges:
            indeg[v] += 1                  # v is reachable from somewhere
        return [i for i in range(n) if indeg[i] == 0]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n + E): one pass over the edges and one over the vertices.
💾 Space Complexity
O(n) for the in-degree array.

⚠️ Interview Pitfalls & Follow-ups

  • Returning all vertices: only the in-degree-zero ones are necessary.
  • Worrying about transitivity: in a DAG, every node with in-degree > 0 is reachable from some source.
  • Using the out-degree instead: the condition is about incoming edges.
  • Assuming the answer must be a single vertex: there can be several sources.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems