Skip to content

2192. All Ancestors of a Node in a Directed Acyclic Graph 👍

  • Time: $O(|\texttt{edges}|)$
  • Space: $O(|\texttt{edges}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
 public:
  vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
    vector<vector<int>> ans(n);
    vector<vector<int>> graph(n);

    for (const auto& e : edges)
      graph[e[0]].push_back(e[1]);

    for (int i = 0; i < n; ++i)
      dfs(graph, i, i, vector<bool>(n), ans);

    return ans;
  }

 private:
  void dfs(const vector<vector<int>>& graph, int u, int ancestor,
           vector<bool>&& seen, vector<vector<int>>& ans) {
    seen[u] = true;
    for (const int v : graph[u]) {
      if (seen[v])
        continue;
      ans[v].push_back(ancestor);
      dfs(graph, v, ancestor, move(seen), ans);
    }
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
  public List<List<Integer>> getAncestors(int n, int[][] edges) {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer>[] graph = new List[n];

    for (int i = 0; i < n; ++i) {
      ans.add(new ArrayList<>());
      graph[i] = new ArrayList<>();
    }

    for (int[] e : edges)
      graph[e[0]].add(e[1]);

    for (int i = 0; i < n; ++i)
      dfs(graph, i, i, new boolean[n], ans);

    return ans;
  }

  private void dfs(List<Integer>[] graph, int u, int ancestor, boolean[] seen,
                   List<List<Integer>> ans) {
    seen[u] = true;
    for (final int v : graph[u]) {
      if (seen[v])
        continue;
      ans.get(v).add(ancestor);
      dfs(graph, v, ancestor, seen, ans);
    }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
  def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:
    ans = [[] for _ in range(n)]
    graph = [[] for _ in range(n)]

    for u, v in edges:
      graph[u].append(v)

    def dfs(u: int, ancestor: int, seen: Set[int]) -> None:
      seen.add(u)
      for v in graph[u]:
        if v in seen:
          continue
        ans[v].append(ancestor)
        dfs(v, ancestor, seen)

    for i in range(n):
      dfs(i, i, set())

    return ans