一、题目

1、题目描述

给你一个正整数 n ，它表示一个 有向无环图 中节点的数目，节点编号为 0 到 n - 1 （包括两者）。

给你一个二维整数数组 edges ，其中 edges[i] = [fromi, toi] 表示图中一条从 fromi 到 toi 的单向边。

请你返回一个数组 answer，其中 answer[i]是第 i 个节点的所有 祖先 ，这些祖先节点 升序 排序。

如果 u 通过一系列边，能够到达 v ，那么我们称节点 u 是节点 v 的 祖先 节点。

2、接口描述

python3

​

class Solution:
    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:

cpp

​

class Solution {
public:
    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
        
    }
};

3、原题链接

2192. 有向无环图中一个节点的所有祖先

---

二、解题报告

1、思路分析

注意到点数不超过1000，边数不超过2000

那么我们可以反向建图，然后对每个点进行dfs，对于遍历到的点就是原图中的ancestors

2、复杂度

时间复杂度： O(n(n + m))空间复杂度：O(n + m)

3、代码详解

python3

​

class Solution:
    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        g = [[] for _ in range(n)]
        for x, y in edges:
            g[y].append(x)
        def dfs(x: int) -> None:
            vis[x] = True
            for y in g[x]:
                if not vis[y]:
                    dfs(y)
        ret = [None] * n
        for i in range(n):
            vis = [False] * n
            dfs(i)
            vis[i] = False
            ret[i] = [j for j, x in enumerate(vis) if x]
        return ret

cpp

​

class Solution {
public:
    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
        vector<vector<int>> g(n);
        for(auto& e : edges)
            g[e[1]].emplace_back(e[0]);
        vector<vector<int>> ret(n);
        vector<bool> vis(n);
        function<void(int)> dfs = [&](int x){
            vis[x] = 1;
            for(int y : g[x])
                if(!vis[y])
                    dfs(y);
        };
        for(int i = 0; i < n; i++) {
            fill(vis.begin(), vis.end(), false);
            dfs(i), vis[i] = false;
            for(int j = 0; j < n; j++)
                if(vis[j])
                    ret[i].emplace_back(j);
        }
        return ret;
    };
};