可以到达所有点的最少点数目 图解题解
这道题到底在问什么
- 输入
- n=6, edges=[[0,1],[0,2],[2,5],[3,4],[4,2]]
- 输出
- [0,3]
- 输入
- n=5, edges=[[0,1],[2,1],[3,1],[1,4],[2,4]]
- 输出
- [0,2,3]
最优解：一步一步想明白
- 3记住「入度为 0 的点必须当起点,其余都能被人到达」,下面逐帧统计入度。
- 4先看这张有向图。一开始每个点的入度都记 0(节点上方数字)。我们沿每条边走一遍:边 a→b 会让 b 的入度加 1。处理完就知道谁「有人指向」、谁「没人指向」。
- 5看边 0→1(高亮):它从 0 指向 1,说明 1 有人能到达。
- 6给 1 的入度 +1,现在 1 的入度 = 1。入度 ≥ 1 意味着 1 不必当起点(总有人能到它)。
- 7看边 0→2(高亮):它从 0 指向 2,说明 2 有人能到达。
- 8给 2 的入度 +1,现在 2 的入度 = 1。入度 ≥ 1 意味着 2 不必当起点(总有人能到它)。
- 9看边 2→5(高亮):它从 2 指向 5,说明 5 有人能到达。
- 10给 5 的入度 +1,现在 5 的入度 = 1。入度 ≥ 1 意味着 5 不必当起点(总有人能到它)。
- 11看边 3→4(高亮):它从 3 指向 4,说明 4 有人能到达。
- 12给 4 的入度 +1,现在 4 的入度 = 1。入度 ≥ 1 意味着 4 不必当起点(总有人能到它)。
- 13看边 4→2(高亮):它从 4 指向 2,说明 2 有人能到达。
- 14给 2 的入度 +1,现在 2 的入度 = 2。入度 ≥ 1 意味着 2 不必当起点(总有人能到它)。
- 15所有 5 条边处理完,入度表建好了:节点 1、2、4、5 都有入边(入度 ≥ 1),只有 0 和 3 的入度还是 0。下面逐个点确认。
- 16节点 0 入度 0:没有任何箭头指向它,谁也到不了,必须选它当起点。加入起点集(右侧)。
- 17节点 1 入度 1 ≥ 1:有上游能到达它,顺着入边往上最终能从某个入度 0 的点走到,不必当起点,跳过。
- 18节点 2 入度 2 ≥ 1:有上游能到达它,顺着入边往上最终能从某个入度 0 的点走到,不必当起点,跳过。
- 19节点 3 入度 0:没有任何箭头指向它,谁也到不了,必须选它当起点。加入起点集(右侧)。
- 20节点 4 入度 1 ≥ 1:有上游能到达它,顺着入边往上最终能从某个入度 0 的点走到,不必当起点,跳过。
- 21节点 5 入度 1 ≥ 1:有上游能到达它,顺着入边往上最终能从某个入度 0 的点走到,不必当起点,跳过。
- 22扫描完毕。入度为 0 的点是 0、3,它们组成最小起点集 [0,3]。先看从 0 出发:沿边能到 1、2、再到 5。
- 23再看从 3 出发:沿边到 4、再到 2、5。两个起点合起来正好覆盖全部 6 个节点,一个都不少、也一个都不能省。这就是答案 [0,3]。
⚠️ 容易写错的地方
✗ 错：想用 DFS/BFS 去算每个点能到哪些点
✓ 对：只需统计入度,挑入度为 0 的
本题不必真的遍历可达集;入度为 0 是「必须当起点」的充要条件,直接 O(n+e) 出答案
✗ 错：把出度为 0 的点当答案
✓ 对：是入度为 0(没人指向),不是出度
出度为 0 是「到不了别人」的汇点,和「必须当起点」无关,方向搞反就全错
✗ 错：担心入度为 0 的点之间互相覆盖
✓ 对：入度为 0 的点谁也到不了它,必须全选
它们之间没有边能互相到达,一个都不能省,所以最小集就是它们全体
完整代码（Python / C++ / Java）
Python
from typing import List
class Solution:
def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:
indeg = [0] * n
for _, b in edges:
indeg[b] = 1
return [i for i, v in enumerate(indeg) if v == 0]C++
#include <vector>
using namespace std;
class Solution {
public:
vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) {
vector<int> indeg(n);
for (auto &e : edges) indeg[e[1]] = 1;
vector<int> ans;
for (int i = 0; i < n; ++i) if (!indeg[i]) ans.push_back(i);
return ans;
}
};Java
import java.util.*;
class Solution {
public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
int[] indeg = new int[n];
for (List<Integer> e : edges) indeg[e.get(1)] = 1;
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < n; i++) if (indeg[i] == 0) ans.add(i);
return ans;
}
}复杂度
时间
O(n+e)
遍历 e 条边标记入度 O(e),再扫 n 个点收集 O(n)
空间
O(n)
一个长度 n 的入度标记数组(结果数组不计入额外空间)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 可以到达所有点的最少点数目 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这和拓扑排序有什么关系?+
密切相关。拓扑排序也从入度为 0 的点起步,本题相当于只取拓扑排序的「第一层源点」。区别是拓扑排序要把所有点排出线性序、会随着删点动态更新入度,而本题只关心初始入度为 0 的点,不需要真的排序,所以更简单、O(n+e) 一遍即可。
如果图可能有环,这题还能这么做吗?+
不能直接做。有环时要先用 Tarjan/Kosaraju 求强连通分量,把每个环缩成一个点得到「缩点 DAG」,再在缩点图上取入度为 0 的分量,每个这样的分量里任选一个原始点即可。本题保证 DAG,省去了缩点这步。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 可以到达所有点的最少点数目 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。