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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

All Ancestors of a Node in a Directed Acyclic Graph

Difficulty: Medium

Problem Description

You are given a positive integer n representing the number of nodes of a Directed Acyclic Graph (DAG). The nodes are numbered from 0 to n - 1 (inclusive). You are also given a 2D integer array edges, where edges[i] = [from_i, to_i] denotes that there is a unidirectional edge from from_i to to_i in the graph. Return a list answer, where answer[i] is the list of ancestors of the i-th node, sorted in ascending order. A node u is an ancestor of another node v if u can reach v via a set of edges.

Key Insights

  • The problem involves traversing a Directed Acyclic Graph (DAG) to identify all ancestors for each node.
  • The graph is directed and acyclic, meaning there are no cycles and edges have a direction.
  • Depth-First Search (DFS) or Breadth-First Search (BFS) can be employed to find all reachable nodes from each node.
  • An adjacency list representation can be used to easily manage the graph structure and perform traversals.

Space and Time Complexity

Time Complexity: O(n + e), where n is the number of nodes and e is the number of edges, due to the traversal of the graph. Space Complexity: O(n + e) for the adjacency list and O(n) for the ancestor lists.

Solution

To solve the problem, we can use Depth-First Search (DFS) for each node to explore all its ancestors. We will maintain an adjacency list to represent the graph. For each node, we will traverse its ancestors recursively, collecting unique ancestors in a set (to avoid duplicates) and then sort the results before returning them.

Code Solutions

def findAncestors(n, edges):
    from collections import defaultdict
    
    # Create an adjacency list
    graph = defaultdict(list)
    for from_node, to_node in edges:
        graph[to_node].append(from_node)  # Reverse the edge direction for ancestors

    # Result list
    answer = [[] for _ in range(n)]

    # Function to perform DFS and find ancestors
    def dfs(node, visited, ancestors):
        for ancestor in graph[node]:
            if ancestor not in visited:
                visited.add(ancestor)
                ancestors.add(ancestor)
                dfs(ancestor, visited, ancestors)

    # Iterate through each node to find its ancestors
    for i in range(n):
        visited = set()
        ancestors = set()
        dfs(i, visited, ancestors)
        answer[i] = sorted(ancestors)  # Sort ancestors for the output

    return answer
← Back to All Questions