在有向无环图（DAG）中，查找每个节点的所有祖先可以通过深度优先搜索（DFS）来实现。第2192题是一个关于在DAG中确定所有节点祖先的问题，可以通过以下步骤解决：

问题描述

给定一个有向无环图，找出图中每个节点的所有祖先。也就是说，对于每个节点v，找出所有可以通过边到达v的节点。

输入

• 一个整数n表示图中节点的数量。
• 一个二维列表edges，其中edges[i] = [u, v]表示从u到v的有向边。

输出

• 返回一个二维列表，其中第i个列表包含节点i的所有祖先节点，以升序排列。

解题步骤

1. 图的表示：使用邻接列表来表示图。例如，对于每个节点i，构造一个列表来存储其“孩子”节点。

2. 反向图的构建：为了方便找到所有祖先，先构造反向图（将每条边的方向反转），这样我们就可以从某个节点出发，找到所有能到达它的节点。这极大简化了逆向思考过程。

3. 深度优先搜索（DFS）：

   • 对于反向图中每个节点，执行DFS以找到所有可达祖先。
   • 使用集合来存储访问过的祖先，以避免重复访问，也便于最终的排序。

4. 排序：因为需要以升序输出每个节点的祖先列表，记得在处理后对每个结果集进行排序。

5. 优化思路（可选）：

   • 为了提高性能（尤其在节点数目非常大时），可以尝试记忆化搜索，即在DFS过程中存储中间结果，避免重复计算。

示例代码

def findAncestors(n, edges):  
    from collections import defaultdict  
    # 创建反向图  
    reverse_graph = defaultdict(list)  
    for u, v in edges:  
        reverse_graph[v].append(u)  
    # 存储每个节点的祖先集合  
    ancestors = [set() for _ in range(n)]  
    # 深度优先搜索  
    def dfs(node, start):  
        for ancestor in reverse_graph[node]:  
            if ancestor not in ancestors[start]:  
                ancestors[start].add(ancestor)  
                dfs(ancestor, start)  
    # 对于每个节点，找出所有祖先  
    for i in range(n):  
        dfs(i, i)  
    # 将结果转换为排好序的列表  
    result = [sorted(list(ans)) for ans in ancestors]  
    return result  
# 示例使用  
n = 4  
edges = [[0, 1], [1, 2], [1, 3]]  
print(findAncestors(n, edges))  

代码说明

• reverse_graph用于保存反向图的信息。
• ancestors列表用于存储每个节点的祖先。
• 通过DFS更新每个节点的祖先集合，然后将结果排序并返回。

这样的方法可以有效地解决问题，并且在面对较大规模的数据时也保持了良好的性能表现。