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

链接：2192.有向无环图中一个节点的所有祖先
难度：Medium
标签：深度优先搜索、广度优先搜索、图、拓扑排序
简介：请你返回一个数组 answer，其中 answer[i]是第 i 个节点的所有 祖先 ，这些祖先节点 升序 排序。

题解 1 - python

• 编辑时间：2024-04-04
• 执行用时：112ms
• 内存消耗：35.63MB
• 编程语言：python
• 解法介绍：dfs。

class Solution:
    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        nodes=[[] for _ in range(n)]
        for f, t in edges:
            nodes[t].append(f)
        @cache
        def dfs(node):
            ans = []
            for f in nodes[node]:
                ans += [f] + dfs(f)
            return sorted(set(ans))
        return [dfs(i) for i in range(n)]