All Ancestors Of A Node In A Directed Acyclic Graph - Leetcode Solution

Problem Statement:

Given a Directed Acyclic Graph (DAG) and a source node, find all the ancestors of the given node in the graph.

Solution:

Approach: One way to solve this problem is to use Depth First Search (DFS) algorithm to traverse the graph and keep track of all the ancestor nodes of the given node. The approach can be summarized in the following steps:

1. Create an empty list to store the ancestor nodes of the given node.
2. Perform DFS on the graph starting from the given node.
3. For every visited node during the DFS, check if it is an ancestor of the given node.
4. If a node is an ancestor, add it to the list of ancestors.
5. Return the list of ancestors.

Input:

The input to the problem is the adjacency list of the DAG and the source node.

Output:

The output of the problem should be the list of all ancestor nodes of the given node.

Code:

Here's the implementation of the solution in Python:

class Graph:
    def __init__(self, vertices):
        self.adj_list = {v: [] for v in vertices}
        self.vertices = vertices
        
    def add_edge(self, start, end):
        self.adj_list[start].append(end)
    
    def get_ancestors(self, source):
        visited = set()
        ancestors = []
        
        def dfs(node):
            visited.add(node)
            
            if node == source:
                return True
            
            for neighbor in self.adj_list[node]:
                if neighbor not in visited and dfs(neighbor):
                    ancestors.append(node)
                    return True
            
            return False
        
        for v in self.vertices:
            if v not in visited:
                dfs(v)
        
        return ancestors

Time Complexity:

The time complexity of the solution is O(V+E), where V is the number of vertices and E is the number of edges in the graph. This is because we are performing a DFS on the graph, and the time complexity of DFS is O(V+E).

Space Complexity:

The space complexity of the solution is O(V), where V is the number of vertices in the graph. This is because we are storing the ancestors in a list, which can have at most V-1 elements. The space complexity of the DFS is also O(V), because we are using a set to store the visited nodes.

1