3 minute read

Problem Statement

2192

Intuition

To solve this problem, the key is to determine all the ancestors of each node in a directed acyclic graph (DAG). An ancestor of a node is any other node that has a path leading to that node. We can use depth-first search (DFS) to explore all paths leading to each node.

Approach

  1. Graph Representation: Represent the graph using an adjacency list where each node points to its direct ancestors.
  2. DFS Traversal: Use DFS to explore all ancestors for each node. Keep track of visited nodes to avoid redundant calculations.
  3. Result Compilation: Store and sort the list of ancestors for each node.

Complexity

  • Time Complexity:

    • Constructing the graph: (O(E)), where (E) is the number of edges.
    • DFS traversal: In the worst case, we visit all nodes for each node, resulting in (O(V^2)), where (V) is the number of nodes.
    • Sorting ancestors for each node: (O(V \log V)).
    • Overall, the time complexity is (O(V^2 + E + V \log V)).
  • Space Complexity:

    • The space for storing ancestors: (O(V^2)) in the worst case.
    • The space for the DFS stack and visited set: (O(V)).
    • Overall, the space complexity is (O(V^2)).

Code

from collections import defaultdict
from typing import List

class Solution:
    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        ancestors = defaultdict(list)

        # Build the graph with adjacency list
        for src, dest in edges:
            ancestors[dest].append(src)

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

        res = []
        for i in range(n):
            visited = set()
            dfs(i, visited)
            res.append(sorted(visited))

        return res

Editorial

Approach 1: Depth First Search (Reversed Graph)

class Solution:
    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        # Initialize adjacency list for the graph
        adjacency_list = [[] for _ in range(n)]

        # Populate the adjacency list with reversed edges
        for edge in edges:
            from_node, to_node = edge
            adjacency_list[to_node].append(from_node)

        ancestors_list = []

        # For each node, find all its ancestors (children in reversed graph)
        for i in range(n):
            ancestors = []
            visited = set()
            self.find_children(i, adjacency_list, visited)
            # Add visited nodes to the current nodes' ancestor list
            for node in range(n):
                if node == i:
                    continue
                if node in visited:
                    ancestors.append(node)
            ancestors_list.append(ancestors)

        return ancestors_list

    # Helper method to perform DFS and find all children of a given node
    def find_children(self, current_node, adjacency_list, visited_nodes):
        # Mark current node as visited
        visited_nodes.add(current_node)

        # Recursively traverse all neighbors
        for neighbour in adjacency_list[current_node]:
            if neighbour not in visited_nodes:
                self.find_children(neighbour, adjacency_list, visited_nodes)

Approach 2: Depth First Search (Optimized)

class Solution:
    def getAncestors(self, n, edges):
        # Initialize adjacency list for each node and ancestors list
        adjacency_list = [[] for _ in range(n)]
        ancestors = [[] for _ in range(n)]

        # Populate the adjacency list with edges
        for edge in edges:
            from_node = edge[0]
            to_node = edge[1]
            adjacency_list[from_node].append(to_node)

        # Perform DFS for each node to find all its ancestors
        for i in range(n):
            self.find_ancestors_DFS(i, adjacency_list, i, ancestors)

        return ancestors

    # Helper method to perform DFS and find ancestors
    def find_ancestors_DFS(
        self, ancestor, adjacency_list, current_node, ancestors
    ):
        for child_node in adjacency_list[current_node]:
            # Check if the ancestor is already added to avoid duplicates
            if (
                not ancestors[child_node]
                or ancestors[child_node][-1] != ancestor
            ):
                ancestors[child_node].append(ancestor)
                self.find_ancestors_DFS(
                    ancestor, adjacency_list, child_node, ancestors
                )

Approach 3: Topological Sort (BFS)

class Solution:
    def getAncestors(self, n, edges):
        # Create adjacency list
        adjacency_list = [[] for _ in range(n)]

        # Fill the adjacency list and indegree array based on the edges
        indegree = [0 for _ in range(n)]
        for edge in edges:
            from_node = edge[0]
            to = edge[1]
            adjacency_list[from_node].append(to)
            indegree[to] += 1

        # Queue for nodes with no incoming edges (starting points for topological sort)
        nodes_with_zero_indegree = [i for i in range(n) if indegree[i] == 0]

        # List to store the topological order of nodes
        topological_order = []
        while nodes_with_zero_indegree:
            current_node = nodes_with_zero_indegree.pop(0)
            topological_order.append(current_node)

            # Reduce indegree of neighboring nodes and add them to the queue
            # if they have no more incoming edges
            for neighbor in adjacency_list[current_node]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0:
                    nodes_with_zero_indegree.append(neighbor)

        # Initialize the result list and set list for storing ancestors
        ancestors_list = [[] for _ in range(n)]
        ancestors_set_list = [set() for _ in range(n)]

        # Fill the set list with ancestors using the topological order
        for node in topological_order:
            for neighbor in adjacency_list[node]:
                # Add immediate parent, and other ancestors.
                ancestors_set_list[neighbor].add(node)
                ancestors_set_list[neighbor].update(ancestors_set_list[node])

        # Convert sets to lists and sort them
        for i in range(n):
            ancestors_list[i].extend(ancestors_set_list[i])
            ancestors_list[i].sort()

        return ancestors_list