How do I determine which nodes must be included to reach all nodes in a DAG?

Focus on nodes with zero incoming edges. These are the only nodes that cannot be reached from any other node and must be part of the minimal set.

Can the minimal set include nodes with incoming edges?

No, nodes with incoming edges are reachable from other nodes, so including them is unnecessary for the minimal set.

Does the order of nodes in the output matter?

No, the problem allows any order of vertices as long as the minimal set covers all nodes.

What is the best time complexity to solve the Minimum Number of Vertices to Reach All Nodes problem?

Using in-degree counting, you can achieve O(n + m) time complexity, scanning all nodes and edges only once.

Why is the solution guaranteed to be unique?

Because each node without incoming edges must be included and all others are reachable from them, forming a deterministic minimal set.

#1557

Medium

auto_awesome图

LeetCode 题解工作台

可以到达所有点的最少点数目

给你一个有向无环图， n 个节点编号为 0 到 n-1 ，以及一个边数组 edges ，其中 edges[i] = [from i , to i ] 表示一条从点 from i 到点 to i 的有向边。找到最小的点集使得从这些点出发能到达图中所有点。题目保证解存在且唯一。你可以以任意顺序返…

图

题目描述

给你一个 有向无环图 ， n 个节点编号为 0 到 n-1 ，以及一个边数组 edges ，其中 edges[i] = [from_i, to_i] 表示一条从点 from_i 到点 to_i 的有向边。

找到最小的点集使得从这些点出发能到达图中所有点。题目保证解存在且唯一。

你可以以任意顺序返回这些节点编号。

示例 1：

输入：n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]
输出：[0,3]
解释：从单个节点出发无法到达所有节点。从 0 出发我们可以到达 [0,1,2,5] 。从 3 出发我们可以到达 [3,4,2,5] 。所以我们输出 [0,3] 。

示例 2：

输入：n = 5, edges = [[0,1],[2,1],[3,1],[1,4],[2,4]]
输出：[0,2,3]
解释：注意到节点 0，3 和 2 无法从其他节点到达，所以我们必须将它们包含在结果点集中，这些点都能到达节点 1 和 4 。

提示：

2 <= n <= 10^5
1 <= edges.length <= min(10^5, n * (n - 1) / 2)
edges[i].length == 2
0 <= from_i, to_i < n
所有点对 (from_i, to_i) 互不相同。

lightbulb

解题思路

方法一：统计入度为 0 的点

我们注意到，所有入度为 $0$ 的点都一定属于最小点集，因为它们没有任何入边。而由于题目给定的是一张有向无环图，因此所有入度不为 $0$ 的点一定存在一条入边，也即一定能从某个入度为 $0$ 的点出发到达。因此我们只需要找到所有入度为 $0$ 的点即可。

时间复杂度 $O(n + m)$ ，空间复杂度 $O(n)$ 。其中 $n$ 和 $m$ 分别是节点数和边数。

1

2

3

4

5

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]

speed

复杂度分析

指标	值
时间	complexity is O(n + m) where n is the number of nodes and m is the number of edges, as each edge is inspected once to compute in-degrees. Space complexity is O(n) to store in-degree counts and the result set of source vertices.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for nodes with no incoming edges as a hint for mandatory inclusion.
question_mark
Consider in-degree counting to avoid full traversal of the DAG.
question_mark
Check that adding any other node does not reduce the minimal vertex set size.

warning

常见陷阱

外企场景

error
Assuming any node can be included without checking in-degree may lead to non-minimal sets.
error
Forgetting that DAG property guarantees a unique minimal solution, leading to unnecessary complexity.
error
Attempting full BFS/DFS from every node increases time and risks TLE for large graphs.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the minimum set of vertices to reach all nodes in a graph that may have cycles, requiring cycle detection.
arrow_right_alt
Compute the minimal vertex set in a weighted DAG where edges have costs, prioritizing coverage by minimal total weight.
arrow_right_alt
Determine the smallest vertex set for a dynamic DAG where edges are added incrementally and the set must be updated efficiently.

help

常见问题

外企场景

继续练习

#1579 保证图可完全遍历 #1584 连接所有点的最小费用 #1591 奇怪的打印机 II