有向无环图中一个节点的所有祖先 图解题解

这道题到底在问什么

输入

n=6, edges=[[0,2],[0,3],[1,3],[2,4],[3,4],[3,5],[4,5]]

输出

[[],[],[0],[0,1],[0,1,2,3],[0,1,2,3,4]]

输入

n=1, edges=[]

输出

[[]]

先想最直接的笨办法

记牢这一句:枚举源点、正向 BFS、够到谁就给谁记上这个源点。源点从小到大跑,答案自然升序。下面从 0 号开始一个源点一个源点地扩散。（动画第 3 步）

最优解：一步一步想明白

1. 3记牢这一句:枚举源点、正向 BFS、够到谁就给谁记上这个源点。源点从小到大跑,答案自然升序。下面从 0 号开始一个源点一个源点地扩散。
2. 4目标:为每个节点求出它的全部祖先,升序排好先把这张图看懂。六个圆圈是编号 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。下面一步步把它推出来。
3. 5源点 0 入队,准备把能到达的节点都记上祖先 0外层循环从 0 号开始。我们不去为每个节点反向找祖先,而是反过来想:从 0 号出发,顺着箭头能走到的每一个节点,0 号都是它的祖先。所以对 0 号做一次正向 BFS,把 0 号入队。右边这张祖先表现在还都是空的,这一轮就要往里填 0。
4. 6当前处理 0 号,依次检查它的出边从队首取出 0 号,看它的出边。0 号指向 2 号和 3 号,按顺序一个个够过去。
5. 72 号第一次被 0 号够到,ans[2] 追加 0 → 0顺着 0 号的箭头走到 2 号,这是它第一次被源点 0 号够到。既然从 0 号能走到这里,0 号就是 2 号的一个祖先,把 0 记进 2 号的祖先表。2 号还要接着往下传,先放进队列排队。
6. 83 号第一次被 0 号够到,ans[3] 追加 0 → 0顺着 0 号的箭头走到 3 号,这是它第一次被源点 0 号够到。既然从 0 号能走到这里,0 号就是 3 号的一个祖先,把 0 记进 3 号的祖先表。3 号还要接着往下传,先放进队列排队。
7. 9当前处理 2 号,依次检查它的出边出队 2 号,检查它的出边。2 号只有一条箭头指向 4 号,接下来尝试把源点 0 传到 4 号。
8. 104 号第一次被 0 号够到,ans[4] 追加 0 → 0顺着 2 号的箭头走到 4 号,这是它第一次被源点 0 号够到。既然从 0 号能走到这里,0 号就是 4 号的一个祖先,把 0 记进 4 号的祖先表。4 号还要接着往下传,先放进队列排队。
9. 11当前处理 3 号,依次检查它的出边出队 3 号,检查它的出边。3 号指向 4 号和 5 号,先遇到本轮已到过的 4 号,再继续看 5 号。
10. 124 号在这一轮已经被 0 号够到过,不重复记从 3 号也能指到 4 号,但 4 号在这一轮 BFS 里已经被标记过了。vis 记号在这里发挥作用:同一个源点对同一个节点只记一次,避免在这种多条路都通的地方把 0 号重复写进祖先表。
11. 135 号第一次被 0 号够到,ans[5] 追加 0 → 0顺着 3 号的箭头走到 5 号,这是它第一次被源点 0 号够到。既然从 0 号能走到这里,0 号就是 5 号的一个祖先,把 0 记进 5 号的祖先表。5 号还要接着往下传,先放进队列排队。
12. 14当前处理 4 号,依次检查它的出边出队 4 号,检查它的出边。4 号指向 5 号,但 5 号已在本轮被源点 0 到达过,后面会跳过这次重复记录。
13. 155 号在这一轮已经被 0 号够到过,不重复记从 4 号也能指到 5 号,但 5 号在这一轮 BFS 里已经被标记过了。vis 记号在这里发挥作用:同一个源点对同一个节点只记一次,避免在这种多条路都通的地方把 0 号重复写进祖先表。
14. 16当前处理 5 号,依次检查它的出边出队 5 号,它没有出边,源点 0 这一轮 BFS 到这里就结束了。
15. 170 号是 2、3、4、5 号的祖先0 号这一轮 BFS 全部跑完。它顺着边够到了 2、3、4、5 号,这四个节点的祖先表里现在都有 0 了。你看,一次 BFS 就把一个源点对所有后代的贡献一次性记完,这正是正向扩散的省事之处。轮到下一个源点 1 号。
16. 18源点 1 入队,准备把能到达的节点都记上祖先 1换源点 1 号,同样做一次正向 BFS。注意这是新的一轮,vis 记号全部清零重来,只是祖先表还留着上一轮填的 0。1 号只有一条出边,指向 3 号。
17. 193 号第一次被 1 号够到,ans[3] 追加 1 → 0, 11 号顺着箭头够到 3 号,3 号第一次被 1 号碰到,把 1 追加到它的祖先表。注意此刻 3 号的祖先表变成 0 和 1,是升序的,因为我们先跑的源点 0、后跑源点 1,追加顺序天然从小到大。
18. 204 号第一次被 1 号够到,ans[4] 追加 1 → 0, 1从 3 号继续往下,4 号也第一次被源点 1 号够到,把 1 追加进 4 号的祖先表,现在是 0, 1。
19. 215 号第一次被 1 号够到,ans[5] 追加 1 → 0, 1从 3 号继续往下,5 号也第一次被源点 1 号够到,把 1 追加进 5 号的祖先表,现在是 0, 1。
20. 221 号是 3、4、5 号的祖先1 号这一轮跑完。它够到了 3、4、5 号,给这三个节点都添上了祖先 1。到这里你能体会到,一个源点管一整片后代,BFS 是把这份影响力铺开的顺手工具。
21. 23源点 2 入队,准备把能到达的节点都记上祖先 2轮到源点 2 号。它有一条出边指向 4 号。做一次正向 BFS,看它能影响到谁。
22. 244 号第一次被 2 号够到,ans[4] 追加 2 → 0, 1, 2从 2 号够到 4 号,4 号第一次被源点 2 号碰到,祖先表追加 2,现在是 0, 1, 2。因为源点是按 0、1、2 的顺序跑的,追加进去自然接在后面,依旧升序。
23. 255 号第一次被 2 号够到,ans[5] 追加 2 → 0, 1, 2从 4 号够到 5 号,5 号第一次被源点 2 号碰到,祖先表追加 2,现在是 0, 1, 2。因为源点是按 0、1、2 的顺序跑的,追加进去自然接在后面,依旧升序。
24. 262 号是 4、5 号的祖先2 号跑完,它够到了 4 号和 5 号,给它们都添上祖先 2。此刻 4 号的祖先表已经攒到 0、1、2,5 号也是 0、1、2,顺序一直是对的。
25. 27源点 3 入队,准备把能到达的节点都记上祖先 3源点 3 号。它有两条出边,指向 4 号和 5 号。继续正向 BFS。
26. 284 号第一次被 3 号够到,ans[4] 追加 3 → 0, 1, 2, 3从 3 号够到 4 号,4 号追加祖先 3,变成 0, 1, 2, 3。
27. 295 号第一次被 3 号够到,ans[5] 追加 3 → 0, 1, 2, 3从 3 号够到 5 号,5 号追加祖先 3,变成 0, 1, 2, 3。
28. 303 号是 4、5 号的祖先3 号跑完,它直接够到 4 号和 5 号,给两者都添上 3。现在 4 号祖先表是 0、1、2、3,离最终答案只差它自己没有更远的祖先了。
29. 31源点 4 入队,准备把能到达的节点都记上祖先 4源点 4 号,它只有一条出边指向 5 号。做最后几步 BFS。
30. 325 号第一次被 4 号够到,ans[5] 追加 4 → 0, 1, 2, 3, 4从 4 号够到 5 号,5 号追加祖先 4,祖先表变成 0, 1, 2, 3, 4。5 号在这么多条路的尽头,把所有能到它的源点都收齐了。
31. 334 号是 5 号的祖先4 号跑完,它够到 5 号,给 5 号添上祖先 4。至此 5 号的祖先表凑齐了 0、1、2、3、4 五个,这正是它的最终答案。
32. 34源点 5 入队,准备把能到达的节点都记上祖先 5最后一个源点 5 号。它在图的最下游,没有任何出边。
33. 355 号谁也够不到,不是任何节点的祖先5 号做 BFS,出队之后发现它没有出边,队列立刻空了,谁也够不到。所以 5 号不是任何节点的祖先,它自己的祖先表倒是最长的一个。六个源点全部跑完了。
34. 36答案 [[],[],[0],[0,1],[0,1,2,3],[0,1,2,3,4]]六个源点全跑完,右边的祖先表就是最终答案:0 号和 1 号在最上游,没有任何祖先,是空表;2 号只有 0;3 号是 0 和 1;4 号收齐了 0 1 2 3;5 号在最下游,收齐了 0 1 2 3 4。回头看每一张表都是升序的,我们从头到尾没有单独排过序,靠的就是外层源点从 0 递增到 n 减 1、追加进去自然从小到大。整道题一句话:与其为每个点反向找祖先,不如枚举源点正向 BFS,够到谁就给谁记上这个源点。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from 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 = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
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

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
        vector<int> g[n];
        for (auto& e : edges) {
            g[e[0]].push_back(e[1]);
        }
        vector<vector<int>> ans(n);
        auto bfs = [&](int s) {
            queue<int> q;
            q.push(s);
            bool vis[n];
            memset(vis, 0, sizeof(vis));
            vis[s] = true;
            while (q.size()) {
                int i = q.front();
                q.pop();
                for (int j : g[i]) {
                    if (!vis[j]) {
                        vis[j] = true;
                        ans[j].push_back(s);
                        q.push(j);
                    }
                }
            }
        };
        for (int i = 0; i < n; ++i) {
            bfs(i);
        }
        return ans;
    }
};

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    private int n;
    private List<Integer>[] g;
    private List<List<Integer>> ans;

    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        g = new List[n];
        this.n = n;
        Arrays.setAll(g, i -> new ArrayList<>());
        for (int[] e : edges) {
            g[e[0]].add(e[1]);
        }
        ans = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            ans.add(new ArrayList<>());
        }
        for (int i = 0; i < n; ++i) {
            bfs(i);
        }
        return ans;
    }

    private void bfs(int s) {
        Deque<Integer> q = new ArrayDeque<>();
        q.offer(s);
        boolean[] vis = new boolean[n];
        vis[s] = true;
        while (!q.isEmpty()) {
            int i = q.poll();
            for (int j : g[i]) {
                if (!vis[j]) {
                    vis[j] = true;
                    q.offer(j);
                    ans.get(j).add(s);
                }
            }
        }
    }
}

复杂度

面试官可能追问