< Back





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

We're given a DAG and asked to return a list of each nodes' parents and their parents parents, etc.
To solve this, we'll use Topological Sort, wherein we don't add a node to the BFS queue until all of
its parents have been visited. We can determine if that's occurred via maintaining a count of the
in degrees for a node and subtracting each time it's visited.

We go ahead and construct a graph from the edges, and add the parents of nodes to the answer. We use
a set to prevent duplicate entries. During our topological sort, we update the child's parents with
the current node's parents, subtract its indegree, and if we have visited all of its parents, we add
it to the queue.

The solution is as follows:


  from collections import defaultdict

  class Solution:
      def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:
          ans = [set() for _ in range(n)]
          ins = [0] * n
          graph = defaultdict(set)

          for u, v in edges:
              ans[v].add(u)
              graph[u].add(v)
              ins[v] += 1

          queue = [i for i, degree in enumerate(ins) if not degree]

          while queue:
              curr_queue, queue = queue, []

              for node in curr_queue:
                  for neighbor in graph[node]:
                      ans[neighbor].update(ans[node])
                      ins[neighbor] -= 1

                      if not ins[neighbor]:
                          queue.append(neighbor)
          
          return [sorted(ancestors) for ancestors in ans]


_ Time Complexity:

  O(n + m) - Where n is the number of nodes and m is the number of edges.

_ Space Complexity:

  O(n) - Where n is the number of nodes - this is the space required to store the queue.