Medium

题目描述

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

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

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

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

示例 1：

输入：n = 8, edges = [[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：

输入：n = 5, edges = [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
输出：[[],[0],[0,1],[0,1,2],[0,1,2,3]]
解释：
上图为输入的图。
- 节点 0 不存在任何祖先。
- 节点 1 有 1 个祖先 0 。
- 节点 2 有 2 个祖先 0 和 1 。
- 节点 3 有 3 个祖先 0 ，1 和 2 。
- 节点 4 有 4 个祖先 0 ，1 ，2 和 3 。

提示：

  • 1 <= n <= 1000
  • 0 <= edges.length <= min(2000, n * (n - 1) / 2)
  • edges[i].length == 2
  • 0 <= fromi, toi <= n - 1
  • fromi != toi
  • 不存在重复边
  • 图是 有向 且 无环 的

解题思路

这道题的核心思路是通过反向思维来解决。我们有两种主要方法：

方法一：正向 DFS（推荐） 对每个节点进行 DFS 遍历，找出它能到达的所有节点，然后将当前节点添加到这些节点的祖先列表中。这样做的好处是，我们从每个节点出发，把自己标记为所有能到达的节点的祖先。

方法二：反向构图 + DFS 将所有边反向，构建一个反向图。然后对每个节点在反向图中进行 DFS，找到所有能到达当前节点的节点，这些就是当前节点的祖先。

我采用方法一，因为它更直观且不需要额外构建反向图。算法步骤：

  1. 构建邻接表表示图
  2. 对每个节点 i，执行 DFS 遍历所有它能到达的节点
  3. 在 DFS 过程中，将节点 i 添加到所有可达节点的祖先列表中
  4. 使用 visited 数组避免重复访问，确保每个节点的祖先列表不包含重复元素
  5. 最后对每个节点的祖先列表进行排序

代码实现

class Solution {
public:
    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
        vector<vector<int>> graph(n);
        vector<vector<int>> result(n);
        
        // 构建邻接表
        for (auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
        }
        
        // 对每个节点进行DFS，找出它能到达的所有节点
        for (int i = 0; i < n; i++) {
            vector<bool> visited(n, false);
            dfs(i, i, graph, result, visited);
        }
        
        // 对结果进行排序
        for (int i = 0; i < n; i++) {
            sort(result[i].begin(), result[i].end());
        }
        
        return result;
    }
    
private:
    void dfs(int ancestor, int curr, vector<vector<int>>& graph, 
             vector<vector<int>>& result, vector<bool>& visited) {
        visited[curr] = true;
        
        for (int next : graph[curr]) {
            if (!visited[next]) {
                result[next].push_back(ancestor);
                dfs(ancestor, next, graph, result, visited);
            }
        }
    }
};

class Solution:
    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        graph = [[] for _ in range(n)]
        result = [[] for _ in range(n)]
        
        # 构建邻接表
        for from_node, to_node in edges:
            graph[from_node].append(to_node)
        
        # 对每个节点进行DFS
        for i in range(n):
            visited = [False] * n
            self.dfs(i, i, graph, result, visited)
        
        # 对结果进行排序
        for i in range(n):
            result[i].sort()
        
        return result
    
    def dfs(self, ancestor, curr, graph, result, visited):
        visited[curr] = True
        
        for next_node in graph[curr]:
            if not visited[next_node]:
                result[next_node].append(ancestor)
                self.dfs(ancestor, next_node, graph, result, visited)

public class Solution {
    public IList<IList<int>> GetAncestors(int n, int[][] edges) {
        var graph = new List<int>[n];
        var result = new List<int>[n];
        
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
            result[i] = new List<int>();
        }
        
        // 构建邻接表
        foreach (var edge in edges) {
            graph[edge[0]].Add(edge[1]);
        }
        
        // 对每个节点进行DFS
        for (int i = 0; i < n; i++) {
            var visited = new bool[n];
            DFS(i, i, graph, result, visited);
        }
        
        // 对结果进行排序
        for (int i = 0; i < n; i++) {
            result[i].Sort();
        }
        
        return result.Cast<IList<int>>().ToList();
    }
    
    private void DFS(int ancestor, int curr, List<int>[] graph, 
                     List<int>[] result, bool[] visited) {
        visited[curr] = true;
        
        foreach (int next in graph[curr]) {
            if (!visited[next]) {
                result[next].Add(ancestor);
                DFS(ancestor, next, graph, result, visited);
            }
        }
    }
}

var getAncestors = function(n, edges) {
    const graph = Array(n).fill().map(() => []);
    const result = Array(n).fill().map(() => []);
    
    // 构建邻接表
    for (const [from, to] of edges) {
        graph[from].push(to);
    }
    
    // DFS函数
    const dfs = (ancestor, curr, visited) => {
        visited[curr] = true;
        
        for (const next of graph[curr]) {
            if (!visited[next]) {
                result[next].push(ancestor);
                dfs(ancestor, next, visited);
            }
        }
    };
    
    // 对每个节点进行DFS
    for (let i = 0; i < n; i++) {
        const visited = new Array(n).fill(false);
        dfs(i, i, visited);
    }
    
    // 对结果进行排序
    for (let i = 0; i < n; i++) {
        result[i].sort((a, b) => a - b);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n² + nm)其中 m 是边数。对每个节点执行一次 DFS，每次 DFS 最多访问所有节点和边
空间复杂度O(n + m)邻接表存储图需要 O(n + m)，递归栈深度最多 O(n)

相关题目