题目描述
思路解析动画文字版
记牢这一句:枚举源点、正向 BFS、够到谁就给谁记上这个源点。源点从小到大跑,答案自然升序。下面从 0 号开始一个源点一个源点地扩散。
总览 · 一张有向无环图：先把这张图看懂。六个圆圈是编号 0 到 5 的六个节点,箭头是有向边,而且整张图没有环。什么叫祖先,如果顺着箭头能从 u 一路走到 v,u 就是 v 的祖先。比如 0 号指向 2 号、2 号又指向 4 号,那 0 号和 2 号都是 4 号的祖先。题目要为每个节点列出它的全部祖先,还要升序排好。先把答案透个底,最后这六个节点的祖先表会是:0 号空、1 号空、2 号是 0、3 号是 0 和 1、4 号是 0 1 2 3、5 号是 0 1 2 3 4。下面一步步把它推出来。
启动 · 从源点 0 出发做 BFS：外层循环从 0 号开始。我们不去为每个节点反向找祖先,而是反过来想:从 0 号出发,顺着箭头能走到的每一个节点,0 号都是它的祖先。所以对 0 号做一次正向 BFS,把 0 号入队。右边这张祖先表现在还都是空的,这一轮就要往里填 0。
出队 0 号 · 看它指向谁：从队首取出 0 号,看它的出边。0 号指向 2 号和 3 号,按顺序一个个够过去。
到达 2 号 · 记祖先 0：顺着 0 号的箭头走到 2 号,这是它第一次被源点 0 号够到。既然从 0 号能走到这里,0 号就是 2 号的一个祖先,把 0 记进 2 号的祖先表。2 号还要接着往下传,先放进队列排队。
到达 3 号 · 记祖先 0：顺着 0 号的箭头走到 3 号,这是它第一次被源点 0 号够到。既然从 0 号能走到这里,0 号就是 3 号的一个祖先,把 0 记进 3 号的祖先表。3 号还要接着往下传,先放进队列排队。
出队 2 号 · 看它指向谁：出队 2 号,检查它的出边。2 号只有一条箭头指向 4 号,接下来尝试把源点 0 传到 4 号。
到达 4 号 · 记祖先 0：顺着 2 号的箭头走到 4 号,这是它第一次被源点 0 号够到。既然从 0 号能走到这里,0 号就是 4 号的一个祖先,把 0 记进 4 号的祖先表。4 号还要接着往下传,先放进队列排队。
出队 3 号 · 看它指向谁：出队 3 号,检查它的出边。3 号指向 4 号和 5 号,先遇到本轮已到过的 4 号,再继续看 5 号。
跳过 4 号 · 本轮已够到：从 3 号也能指到 4 号,但 4 号在这一轮 BFS 里已经被标记过了。vis 记号在这里发挥作用:同一个源点对同一个节点只记一次,避免在这种多条路都通的地方把 0 号重复写进祖先表。
到达 5 号 · 记祖先 0：顺着 3 号的箭头走到 5 号,这是它第一次被源点 0 号够到。既然从 0 号能走到这里,0 号就是 5 号的一个祖先,把 0 记进 5 号的祖先表。5 号还要接着往下传,先放进队列排队。
出队 4 号 · 看它指向谁：出队 4 号,检查它的出边。4 号指向 5 号,但 5 号已在本轮被源点 0 到达过,后面会跳过这次重复记录。
跳过 5 号 · 本轮已够到：从 4 号也能指到 5 号,但 5 号在这一轮 BFS 里已经被标记过了。vis 记号在这里发挥作用:同一个源点对同一个节点只记一次,避免在这种多条路都通的地方把 0 号重复写进祖先表。
出队 5 号 · 看它指向谁：出队 5 号,它没有出边,源点 0 这一轮 BFS 到这里就结束了。
源点 0 完成 · 它是这些节点的祖先：0 号这一轮 BFS 全部跑完。它顺着边够到了 2、3、4、5 号,这四个节点的祖先表里现在都有 0 了。你看,一次 BFS 就把一个源点对所有后代的贡献一次性记完,这正是正向扩散的省事之处。轮到下一个源点 1 号。
启动 · 从源点 1 出发做 BFS：换源点 1 号,同样做一次正向 BFS。注意这是新的一轮,vis 记号全部清零重来,只是祖先表还留着上一轮填的 0。1 号只有一条出边,指向 3 号。
到达 3 号 · 记祖先 1：1 号顺着箭头够到 3 号,3 号第一次被 1 号碰到,把 1 追加到它的祖先表。注意此刻 3 号的祖先表变成 0 和 1,是升序的,因为我们先跑的源点 0、后跑源点 1,追加顺序天然从小到大。
到达 4 号 · 记祖先 1：从 3 号继续往下,4 号也第一次被源点 1 号够到,把 1 追加进 4 号的祖先表,现在是 0, 1。
到达 5 号 · 记祖先 1：从 3 号继续往下,5 号也第一次被源点 1 号够到,把 1 追加进 5 号的祖先表,现在是 0, 1。
源点 1 完成 · 它是这些节点的祖先：1 号这一轮跑完。它够到了 3、4、5 号,给这三个节点都添上了祖先 1。到这里你能体会到,一个源点管一整片后代,BFS 是把这份影响力铺开的顺手工具。
启动 · 从源点 2 出发做 BFS：轮到源点 2 号。它有一条出边指向 4 号。做一次正向 BFS,看它能影响到谁。
到达 4 号 · 记祖先 2：从 2 号够到 4 号,4 号第一次被源点 2 号碰到,祖先表追加 2,现在是 0, 1, 2。因为源点是按 0、1、2 的顺序跑的,追加进去自然接在后面,依旧升序。
到达 5 号 · 记祖先 2：从 4 号够到 5 号,5 号第一次被源点 2 号碰到,祖先表追加 2,现在是 0, 1, 2。因为源点是按 0、1、2 的顺序跑的,追加进去自然接在后面,依旧升序。
源点 2 完成 · 它是这些节点的祖先：2 号跑完,它够到了 4 号和 5 号,给它们都添上祖先 2。此刻 4 号的祖先表已经攒到 0、1、2,5 号也是 0、1、2,顺序一直是对的。
启动 · 从源点 3 出发做 BFS：源点 3 号。它有两条出边,指向 4 号和 5 号。继续正向 BFS。
到达 4 号 · 记祖先 3：从 3 号够到 4 号,4 号追加祖先 3,变成 0, 1, 2, 3。
到达 5 号 · 记祖先 3：从 3 号够到 5 号,5 号追加祖先 3,变成 0, 1, 2, 3。
源点 3 完成 · 它是这些节点的祖先：3 号跑完,它直接够到 4 号和 5 号,给两者都添上 3。现在 4 号祖先表是 0、1、2、3,离最终答案只差它自己没有更远的祖先了。
启动 · 从源点 4 出发做 BFS：源点 4 号,它只有一条出边指向 5 号。做最后几步 BFS。
到达 5 号 · 记祖先 4：从 4 号够到 5 号,5 号追加祖先 4,祖先表变成 0, 1, 2, 3, 4。5 号在这么多条路的尽头,把所有能到它的源点都收齐了。
源点 4 完成 · 它是这些节点的祖先：4 号跑完,它够到 5 号,给 5 号添上祖先 4。至此 5 号的祖先表凑齐了 0、1、2、3、4 五个,这正是它的最终答案。
启动 · 从源点 5 出发做 BFS：最后一个源点 5 号。它在图的最下游,没有任何出边。
源点 5 完成 · 它是这些节点的祖先：5 号做 BFS,出队之后发现它没有出边,队列立刻空了,谁也够不到。所以 5 号不是任何节点的祖先,它自己的祖先表倒是最长的一个。六个源点全部跑完了。
回放 · 六张祖先表全部凑齐：六个源点全跑完,右边的祖先表就是最终答案:0 号和 1 号在最上游,没有任何祖先,是空表;2 号只有 0;3 号是 0 和 1;4 号收齐了 0 1 2 3;5 号在最下游,收齐了 0 1 2 3 4。回头看每一张表都是升序的,我们从头到尾没有单独排过序,靠的就是外层源点从 0 递增到 n 减 1、追加进去自然从小到大。整道题一句话:与其为每个点反向找祖先,不如枚举源点正向 BFS,够到谁就给谁记上这个源点。
边界想清:单点无祖先、无边时人人空表、一条链上上游都是下游的祖先。
面试重点:正向扩散利用「源点能到达即为祖先」、可换拓扑排序传播集合、时间 O(n 乘以括号 n 加 m 括号)。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]: def bfs(s: int): q = deque([s]) vis = {s} while q: i = q.popleft() for j in g[i]: if j not in vis: vis.add(j) q.append(j) ans[j].append(s) g = defaultdict(list) for u, v in edges: g[u].append(v) ans = [[] for _ in range(n)] for i in range(n): bfs(i) return ans复杂度
- 时间：O(n·(n+m))，n 是节点数,m 是边数。对每一个源点都做一次正向 BFS,单次 BFS 最多访问 n 个点、走 m 条边,是 O(n+m);外层跑 n 个源点,合计 O(n 乘以括号 n 加 m 括号)
- 空间：O(n+m)，按辅助空间峰值算。邻接表存全部边是 O(n+m);每一轮 BFS 用的 vis 记号和队列都是 O(n),用完即回收;答案本身最坏可达 O(n 的平方),但那是输出、通常单独计
易错点
面试追问把动画讲成自己的话
追问为什么正向扩散比逐点反向找祖先更好写?
追问除了逐源点 BFS,还有别的解法吗?
追问复杂度是多少,瓶颈在哪?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
统计网格图中没有被保卫的格子数
LeetCode 2257 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题