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

题目

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

给你一个二维整数数组 $edges$ ，其中 $edges[i]=[fro{m}_i,t{o}_i]$ 表示图中一条从 $fro{m}_i$ 到 $t{o}_i$ 的单向边。

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

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

输入：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：

• 节点 0 没有任何祖先。
• 节点 1 有 1 个祖先 0 。
• 节点 2 有 2 个祖先 0 和 1 。
• 节点 3 有 3 个祖先 0 ，1 和 2 。
• 节点 4 有 4 个祖先 0 ，1 ，2 和 3 。

提示：

• $1\le n\le 1000$
• $0\le edges.length\le min(2000,n\ast (n-1)/2)$
• $edges[i].length==2$
• $0\le fro{m}_i,t{o}_i\le n-1$
• $fro{m}_i\ne t{o}_i$
• 图中不会有重边。
• 图是 有向 且 无环 的。

思路

要求找出有向无环图（DAG）中每个节点的所有祖先节点。由于图是无环的，可以使用深度优先搜索（DFS）来解决这个问题

代码

class Solution {
public:
    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
        vector<vector<int>> g(n, vector<int>());
        auto res = g;
        for(const auto& now : edges) {
            int a = now[0], b = now[1];
            g[b].push_back(a);
        }
        vector<bool> vis(n, false);
        function<void(int)> dfs = [&](int ver) {
            if(vis[ver]) return;
            vis[ver] = true;
            for(const auto& toVer : g[ver]) {
                dfs(toVer);
            }
        };
        for(int i = 0; i < n; i++) {
            vis.assign(n, false);
            dfs(i);
            vis[i] = false;
            for(int j = 0; j < n; j++) {
                if(vis[j]) res[i].push_back(j);
            }
        }
        return res;
    }
};

复杂度分析

时间复杂度

$O(n+m)$，其中 $n$ 是节点数，$m$ 是边数。

空间复杂度

$O(n)$，主要是存储邻接表和访问标记数组的空间开销。

结果

总结

通过深度优先搜索（DFS）来解决有向无环图中的祖先节点问题。