LeetCode 题解工作台
有向无环图中一个节点的所有祖先
给你一个正整数 n ，它表示一个 有向无环图 中节点的数目，节点编号为 0 到 n - 1 （包括两者）。 给你一个二维整数数组 edges ，其中 edges[i] = [from i , to i ] 表示图中一条从 from i 到 to i 的单向边。 请你返回一个数组 answer ，其中…
4
题型
6
代码语言
3
相关题
当前训练重点
中等 · 图·搜索
答案摘要
我们先根据二维数组 构建邻接表 ，其中 表示节点 的所有后继节点。 然后我们从小到大枚举节点 作为祖先节点，使用 BFS 搜索节点 的所有后继节点，把节点 加入这些后继节点的祖先列表中。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·搜索 题型思路
题目描述
给你一个正整数 n ，它表示一个 有向无环图 中节点的数目，节点编号为 0 到 n - 1 （包括两者）。
给你一个二维整数数组 edges ，其中 edges[i] = [fromi, toi] 表示图中一条从 fromi 到 toi 的单向边。
请你返回一个数组 answer，其中 answer[i]是第 i 个节点的所有 祖先 ，这些祖先节点 升序 排序。
如果 u 通过一系列边，能够到达 v ，那么我们称节点 u 是节点 v 的 祖先 节点。
示例 1：
输入：n = 8, edgeList = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]] 输出：[[],[],[],[0,1],[0,2],[0,1,3],[0,1,2,3,4],[0,1,2,3]] 解释： 上图为输入所对应的图。 - 节点 0 ，1 和 2 没有任何祖先。 - 节点 3 有 2 个祖先 0 和 1 。 - 节点 4 有 2 个祖先 0 和 2 。 - 节点 5 有 3 个祖先 0 ，1 和 3 。 - 节点 6 有 5 个祖先 0 ，1 ，2 ，3 和 4 。 - 节点 7 有 4 个祖先 0 ，1 ，2 和 3 。
示例 2：
输入：n = 5, edgeList = [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]] 输出：[[],[0],[0,1],[0,1,2],[0,1,2,3]] 解释： 上图为输入所对应的图。 - 节点 0 没有任何祖先。 - 节点 1 有 1 个祖先 0 。 - 节点 2 有 2 个祖先 0 和 1 。 - 节点 3 有 3 个祖先 0 ，1 和 2 。 - 节点 4 有 4 个祖先 0 ，1 ，2 和 3 。
提示：
1 <= n <= 10000 <= edges.length <= min(2000, n * (n - 1) / 2)edges[i].length == 20 <= fromi, toi <= n - 1fromi != toi- 图中不会有重边。
- 图是 有向 且 无环 的。
解题思路
方法一：BFS
我们先根据二维数组 构建邻接表 ，其中 表示节点 的所有后继节点。
然后我们从小到大枚举节点 作为祖先节点，使用 BFS 搜索节点 的所有后继节点，把节点 加入这些后继节点的祖先列表中。
时间复杂度 ，空间复杂度 。其中 是节点数。
class 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^2 + m) |
| 空间 | O(n^2 + m) |
面试官常问的追问
外企场景- question_mark
Ability to apply reverse graph traversal to collect ancestors.
- question_mark
Understanding of topological sorting and how it aids in graph processing.
- question_mark
Knowledge of BFS/DFS and their application in DAGs.
常见陷阱
外企场景- error
Failing to reverse the graph before starting ancestor collection.
- error
Not handling edge cases where nodes have no ancestors.
- error
Inefficient traversal that leads to redundant computations for each node.
进阶变体
外企场景- arrow_right_alt
Consider how reversing the graph affects traversal and memory use.
- arrow_right_alt
Explore the trade-offs between DFS and BFS for this problem.
- arrow_right_alt
Test performance on larger graphs with up to 1000 nodes and 2000 edges.