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
- A vertex must be in the answer if no edge enters it -- nothing can reach it otherwise.
- Conversely, every vertex with a positive in-degree is reachable from some such source (since the graph is a DAG).
- So the answer is exactly the set of vertices with in-degree 0.
- 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.