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

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

• 难度: medium
• 原始链接: https://leetcode.cn/problems/all-ancestors-of-a-node-in-a-directed-acyclic-graph
• 标签: 深度优先遍历

解法一: 深度优先遍历

go

func getAncestors(n int, edges [][]int) [][]int {
  relations := make([][]int, n)
  // 反方向建立联系
  for _, edge := range edges {
    relations[edge[1]] = append(relations[edge[1]], edge[0])
  }
  // 标记已经计算完成的节点
  visit := make([]bool, n)
  // 结果
  ans := make([][]int, n)
  // 计算指定节点的所有父节点，排序并去重
  var dfs func(cur int) []int
  dfs = func(cur int) []int {
    if visit[cur] {
      return ans[cur]
    }
    // 标记当前节点已计算完毕
    visit[cur] = true
    // 记录当前节点的所有父节点，可能会有节点重复
    parent := []int{}
    for _, relation := range relations[cur] {
      parent = append(parent, dfs(relation)...)
      parent = append(parent, relation)
    }
    // 排序
    sort.Ints(parent)
    n := len(parent)
    // 双指针去重
    if n > 0 {
      i := 0
      for j := 1; j < n; j++ {
        if parent[j] != parent[i] {
          i++
          parent[i] = parent[j]
        }
      }
      ans[cur] = parent[:i+1]
    }
    return parent
  }
  // 循环计算每个节点
  for i := 0; i < n; i++ {
    dfs(i)
  }
  return ans
}

java

class Solution {
    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        // 标记已经计算完成的节点
        boolean[] visit = new boolean[n];
        // 反方向建立联系
        Map<Integer, List<Integer>> relations = new HashMap<>(n);
        for (int[] edge : edges) {
            relations.merge(edge[1], Collections.singletonList(edge[0]), (origin, target) -> {
                if (origin.size() == 1) {
                    origin = new ArrayList<>(origin);
                }
                origin.addAll(target);
                return origin;
            });
        }
        List<List<Integer>> ans = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            ans.add(new ArrayList<>());
        }
        // 循环计算每个节点
        for (int i = 0; i < n; i++) {
            this.dfs(i, visit, relations, ans);
        }
        return ans;
    }

    private List<Integer> dfs(int cur, boolean[] visit, Map<Integer, List<Integer>> relations,
            List<List<Integer>> ans) {
        if (visit[cur]) {
            return ans.get(cur);
        }
        // 标记当前节点已计算完毕
        visit[cur] = true;
        // 记录当前节点的所有父节点，可能会有节点重复
        List<Integer> parent = new ArrayList<>();
        for (Integer relation : relations.getOrDefault(cur, Collections.emptyList())) {
            parent.addAll(this.dfs(relation, visit, relations, ans));
            parent.add(relation);
        }
        if (parent.isEmpty()) {
            return parent;
        }
        // 排序
        Collections.sort(parent);
        // 双指针去重
        int i = 0;
        int n = parent.size();
        for (int j = 1; j < n; j++) {
            if (!Objects.equals(parent.get(j), parent.get(i))) {
                parent.set(++i, parent.get(j));
            }
        }
        ans.set(cur, parent.subList(0, i + 1));
        return parent;
    }
}