题目描述
思路解析动画文字版
记住「入度为 0 的点必须当起点,其余都能被人到达」,下面逐帧统计入度。
先看这张有向图。一开始每个点的入度都记 0(节点上方数字)。我们沿每条边走一遍:边 a→b 会让 b 的入度加 1。处理完就知道谁「有人指向」、谁「没人指向」。
看边 0→1(高亮):它从 0 指向 1,说明 1 有人能到达。
给 1 的入度 +1,现在 1 的入度 = 1。入度 ≥ 1 意味着 1 不必当起点(总有人能到它)。
看边 0→2(高亮):它从 0 指向 2,说明 2 有人能到达。
给 2 的入度 +1,现在 2 的入度 = 1。入度 ≥ 1 意味着 2 不必当起点(总有人能到它)。
看边 2→5(高亮):它从 2 指向 5,说明 5 有人能到达。
给 5 的入度 +1,现在 5 的入度 = 1。入度 ≥ 1 意味着 5 不必当起点(总有人能到它)。
看边 3→4(高亮):它从 3 指向 4,说明 4 有人能到达。
给 4 的入度 +1,现在 4 的入度 = 1。入度 ≥ 1 意味着 4 不必当起点(总有人能到它)。
看边 4→2(高亮):它从 4 指向 2,说明 2 有人能到达。
给 2 的入度 +1,现在 2 的入度 = 2。入度 ≥ 1 意味着 2 不必当起点(总有人能到它)。
所有 5 条边处理完,入度表建好了:节点 1、2、4、5 都有入边(入度 ≥ 1),只有 0 和 3 的入度还是 0。下面逐个点确认。
节点 0 入度 0:没有任何箭头指向它,谁也到不了,必须选它当起点。加入起点集(右侧)。
节点 1 入度 1 ≥ 1:有上游能到达它,顺着入边往上最终能从某个入度 0 的点走到,不必当起点,跳过。
节点 2 入度 2 ≥ 1:有上游能到达它,顺着入边往上最终能从某个入度 0 的点走到,不必当起点,跳过。
节点 3 入度 0:没有任何箭头指向它,谁也到不了,必须选它当起点。加入起点集(右侧)。
节点 4 入度 1 ≥ 1:有上游能到达它,顺着入边往上最终能从某个入度 0 的点走到,不必当起点,跳过。
节点 5 入度 1 ≥ 1:有上游能到达它,顺着入边往上最终能从某个入度 0 的点走到,不必当起点,跳过。
扫描完毕。入度为 0 的点是 0、3,它们组成最小起点集 [0,3]。先看从 0 出发:沿边能到 1、2、再到 5。
再看从 3 出发:沿边到 4、再到 2、5。两个起点合起来正好覆盖全部 6 个节点,一个都不少、也一个都不能省。这就是答案 [0,3]。
边界:无边全选;一条链只选链头;单点选自己。
两个延伸:本题是拓扑排序的「源点层」;有环需先缩点再取源。
参考代码
from typing import Listclass 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]复杂度
- 时间：O(n+e)，遍历 e 条边标记入度 O(e),再扫 n 个点收集 O(n)
- 空间：O(n)，一个长度 n 的入度标记数组(结果数组不计入额外空间)
易错点
面试追问把动画讲成自己的话
追问这和拓扑排序有什么关系?
追问如果图可能有环,这题还能这么做吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最小体力消耗路径
LeetCode 1631 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题