We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

All Ancestors of a Node in a Directed Acyclic Graph

Number: 1431

Difficulty: Medium

Paid? No

Companies: Meta, Amazon, Oracle, Google

Problem Description

Given a directed acyclic graph (DAG) with n nodes numbered from 0 to n-1 and a list of directed edges, return for each node a sorted list (in ascending order) of all its ancestors. A node u is considered an ancestor of node v if there is a path from u to v.

Key Insights

  • The problem is set in a DAG, ensuring the existence of a topological order.
  • Propagation of ancestor information can be efficiently managed by processing nodes in topological order.
  • For each node, the ancestors of its parent(s) along with the parent itself form the ancestors of the node.
  • Using sets for each node avoids duplicate ancestors, and sorting each set in the end gives the required output order.

Space and Time Complexity

Time Complexity: O(n + m + (total union operations cost))
  In the worst-case, each union operation may touch up to O(n) elements, leading to an overall bound that is pseudo-polynomial relative to the graph size.
Space Complexity: O(n^2) in the worst-case due to storing ancestors for each node.

Solution

We solve the problem by first computing the in-degrees for all nodes and using a queue to perform a topological sort. For every node processed, we update each of its children:

  • Merge the current node’s ancestor set into the child’s ancestor set.
  • Add the current node as a direct ancestor of the child. After processing all nodes, each node’s ancestor set is converted into a sorted list before returning. This approach leverages the properties of DAGs and ensures that ancestor information is propagated correctly and efficiently.

Code Solutions

# Python solution with line-by-line comments
from collections import defaultdict, deque

def getAncestors(n, edges):
    # Build graph representation and indegree counter
    graph = defaultdict(list)
    indegree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    # Initialize a list of sets for storing ancestors of each node
    ancestors = [set() for _ in range(n)]
    
    # Initialize a queue with nodes having indegree 0 (sources)
    queue = deque()
    for i in range(n):
        if indegree[i] == 0:
            queue.append(i)
    
    # Process nodes in topological order
    while queue:
        node = queue.popleft()
        # For each child of the current node
        for child in graph[node]:
            # Merge current node's ancestors into the child's ancestor set
            ancestors[child].update(ancestors[node])
            # Add the current node as an immediate ancestor of the child
            ancestors[child].add(node)
            # Decrement indegree for child
            indegree[child] -= 1
            # If indegree becomes zero, add child to queue
            if indegree[child] == 0:
                queue.append(child)
    
    # Convert each set of ancestors into sorted list as required
    result = [sorted(list(anc)) for anc in ancestors]
    return result
← Back to All Questions