Naive Solution - Brute Force (Depth-First Search)

For each node, we can perform a Depth-First Search (DFS) or Breadth-First Search (BFS) to find all the nodes that can reach it. These nodes are its ancestors.

Algorithm:

1. Initialize an empty list of lists answer of size n, where answer[i] will store the ancestors of node i.
2. For each node i from 0 to n - 1:
   • Perform a DFS or BFS starting from node i to find all nodes that can reach i.
   • During the traversal, keep track of the nodes visited.
   • Add the visited nodes (excluding i itself) to answer[i].
3. Sort the ancestor list for each node in ascending order.
4. Return answer.

Code (Python):

def get_ancestors_brute_force(n, edges):
    adj_list = [[] for _ in range(n)]
    for u, v in edges:
        adj_list[v].append(u)

    answer = [[] for _ in range(n)]

    def dfs(node, target, visited):
        for neighbor in adj_list[node]:
            if neighbor == target:
                visited.add(node)
            else:
                dfs(neighbor, target, visited)
                if target in visited:
                  visited.add(node)

    for i in range(n):
        visited = set()
        for j in range(n):
            dfs(j,i,visited)

        ancestors = sorted(list(visited))

        answer[i] = ancestors
    return answer

Time Complexity:

• O(n * (n + m)), where n is the number of nodes and m is the number of edges. In the worst case, we might have to traverse all edges for each node.

Space Complexity:

• O(n + m) for the adjacency list and the recursion stack during DFS/BFS, plus O(n) to store the ancestors for each node.

Optimal Solution - Dynamic Programming (Topological Sort)

We can use dynamic programming combined with topological sorting to efficiently determine the ancestors of each node.

Algorithm:

1. Build an adjacency list representation of the graph.
2. Compute the in-degree of each node.
3. Perform a topological sort of the graph using a queue.
4. During the topological sort:
   • Initialize a set ancestors[i] for each node i.
   • When processing a node u, for each neighbor v of u:
     • Add u to the ancestors set of v.
     • Add all ancestors of u to the ancestors of v.
5. After the topological sort, sort the ancestor list for each node in ascending order.
6. Return answer.

Code (Python):

def get_ancestors_optimal(n, edges):
    adj_list = [[] for _ in range(n)]
    in_degree = [0] * n
    for u, v in edges:
        adj_list[u].append(v)
        in_degree[v] += 1

    queue = [i for i in range(n) if in_degree[i] == 0]
    ancestors = [set() for _ in range(n)]

    while queue:
        u = queue.pop(0)
        for v in adj_list[u]:
            ancestors[v].add(u)
            ancestors[v].update(ancestors[u])
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)

    answer = [sorted(list(ancestors[i])) for i in range(n)]
    return answer

Time Complexity:

• O(n + m), where n is the number of nodes and m is the number of edges. The topological sort takes O(n + m) time, and updating ancestors takes O(n) in the worst case for each edge, but the set operations amortize this cost.

Space Complexity:

• O(n + m) for the adjacency list, in-degree array, queue, and ancestor sets.

Edge Cases:

• Empty Graph: If the graph has no edges, each node will have an empty list of ancestors.
• Single Node Graph: If the graph has only one node, its ancestor list will be empty.
• Disconnected Graph: The algorithm will still correctly identify ancestors for each connected component.
• Cyclic Graph: The problem states that the graph is acyclic so there is no need to handle cycles.