---

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

• 标签：图
• 难度：中等

题目链接

• 1557. 可以到达所有点的最少点数目 - 力扣

题目大意

描述：给定一个有向无环图（DAG），编号 $0 \sim n-1$，以及边集 $edges$。

要求：返回最小的顶点集合，使得从这些顶点出发可以到达图中所有顶点。

说明：

• $2 \le n \le 10^5$。
• $1 \le edges.length \le 10^5$。

示例：

• 示例 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 。

解题思路

思路 1：入度统计

1. 核心思想

在有向无环图中，一个顶点如果入度为 $0$，则没有任何其他顶点可以到达它。因此，所有入度为 $0$ 的顶点必须包含在结果集合中。

另一方面，入度非 $0$ 的顶点总可以被某个入度为 $0$ 的顶点（或间接）到达。

因此最小集合就是所有入度为 $0$ 的顶点。

2. 具体步骤

第 1 步：创建一个入度数组 $indeg$，初始全 $0$。

第 2 步：遍历每条边 $[from, to]$，$indeg[to] += 1$。

第 3 步：收集所有 $indeg[i] == 0$ 的顶点。

第 4 步：返回该集合（顺序任意）。

3. 正确性证明

• 入度 $= 0$ 的顶点无法被其他顶点到达，因此必须选入集合。
• 对于入度 $> 0$ 的顶点，沿着入边回溯，最终会到达某个入度为 $0$ 的顶点（DAG 保证无环，所以一定能回溯到源点）。
• 因此选择所有入度为 $0$ 的顶点即可覆盖所有顶点。

4. 举例说明

以 $n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]$ 为例：

0 → 1, 0 → 2 → 5
3 → 4 → 2

入度：

• $0$：入度 $0$
• $1$：入度 $1$（来自 $0$）
• $2$：入度 $2$（来自 $0, 4$）
• $3$：入度 $0$
• $4$：入度 $1$（来自 $3$）
• $5$：入度 $1$（来自 $2$）

入度为 $0$ 的顶点：$0, 3$。

从 $0$ 出发可到达 $1,2,5$。
从 $3$ 出发可到达 $4,2,5$。

所有顶点都被覆盖。返回 $[0,3]$。

以 $n = 3, edges = [[1,2],[1,0],[0,2]]$ 为例：

入度：

• $0$：入度 $1$（来自 $1$）
• $1$：入度 $0$
• $2$：入度 $2$（来自 $1, 0$）

返回 $[1]$。

思路 1：代码

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

思路 1：复杂度分析

• 时间复杂度：$O(n + m)$。
• 空间复杂度：$O(n)$。