Code Implementation

from collections import defaultdict, deque

class Solution:
    def getAncestors(self, n, edges):
        graph = defaultdict(list)
        indegree = [0] * n
        for u, v in edges:
            graph[u].append(v)
            indegree[v] += 1

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

        while queue:
            node = queue.popleft()
            for nei in graph[node]:
                ancestors[nei].update(ancestors[node])
                ancestors[nei].add(node)
                indegree[nei] -= 1
                if indegree[nei] == 0:
                    queue.append(nei)

        return [sorted(list(s)) for s in ancestors]
      

#include <vector>
#include <queue>
#include <set>
using namespace std;

class Solution {
public:
    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
        vector<vector<int>> graph(n);
        vector<int> indegree(n, 0);
        for (auto& e : edges) {
            graph[e[0]].push_back(e[1]);
            indegree[e[1]]++;
        }

        vector<set<int>> ancestors(n);
        queue<int> q;
        for (int i = 0; i < n; ++i)
            if (indegree[i] == 0) q.push(i);

        while (!q.empty()) {
            int node = q.front(); q.pop();
            for (int nei : graph[node]) {
                ancestors[nei].insert(ancestors[node].begin(), ancestors[node].end());
                ancestors[nei].insert(node);
                indegree[nei]--;
                if (indegree[nei] == 0)
                    q.push(nei);
            }
        }

        vector<vector<int>> res(n);
        for (int i = 0; i < n; ++i)
            res[i] = vector<int>(ancestors[i].begin(), ancestors[i].end());
        return res;
    }
};
      

import java.util.*;

class Solution {
    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        int[] indegree = new int[n];
        for (int i = 0; i < n; ++i) graph.add(new ArrayList<>());
        for (int[] e : edges) {
            graph.get(e[0]).add(e[1]);
            indegree[e[1]]++;
        }
        List<Set<Integer>> ancestors = new ArrayList<>();
        for (int i = 0; i < n; ++i) ancestors.add(new HashSet<>());
        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < n; ++i)
            if (indegree[i] == 0) q.offer(i);

        while (!q.isEmpty()) {
            int node = q.poll();
            for (int nei : graph.get(node)) {
                ancestors.get(nei).addAll(ancestors.get(node));
                ancestors.get(nei).add(node);
                indegree[nei]--;
                if (indegree[nei] == 0)
                    q.offer(nei);
            }
        }

        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            List<Integer> temp = new ArrayList<>(ancestors.get(i));
            Collections.sort(temp);
            res.add(temp);
        }
        return res;
    }
}
      

/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number[][]}
 */
var getAncestors = function(n, edges) {
    const graph = Array.from({length: n}, () => []);
    const indegree = Array(n).fill(0);
    for (const [u, v] of edges) {
        graph[u].push(v);
        indegree[v]++;
    }
    const ancestors = Array.from({length: n}, () => new Set());
    const queue = [];
    for (let i = 0; i < n; i++) {
        if (indegree[i] === 0) queue.push(i);
    }
    while (queue.length) {
        const node = queue.shift();
        for (const nei of graph[node]) {
            for (const anc of ancestors[node]) ancestors[nei].add(anc);
            ancestors[nei].add(node);
            indegree[nei]--;
            if (indegree[nei] === 0) queue.push(nei);
        }
    }
    return ancestors.map(s => Array.from(s).sort((a, b) => a - b));
};
      

Problem Description

You are given a directed acyclic graph (DAG) with n nodes labeled from 0 to n - 1 and a list of directed edges edges where each edge is represented as [from, to]. Your task is to find for every node all of its ancestors—meaning all nodes from which there is a directed path to the given node. The ancestors for each node should be returned as a sorted list with no duplicates.

Key constraints:

• There are no cycles in the graph (it's a DAG).
• Return a list where the i-th element is a sorted list of all ancestors of node i.
• Each ancestor should appear only once per node.

Thought Process

At first glance, we might consider running a graph traversal (like DFS or BFS) from every node to find its ancestors. However, this approach would be inefficient, especially for large graphs, since it would involve redundant traversals and repeated work.

Instead, we notice that since the graph is acyclic, we can process nodes in topological order. This means that when we visit a node, all its ancestors have already been processed. We can then propagate ancestor information efficiently from each node to its neighbors.

The core insight is to use a combination of topological sorting and set operations to accumulate and propagate ancestor sets as we traverse the graph, ensuring each ancestor is only recorded once per node.

Solution Approach

We solve the problem using the following steps:

1. Build the Graph:
   • Represent the DAG using an adjacency list for fast neighbor lookups.
   • Track the indegree (number of incoming edges) for each node, which helps with topological sorting.
2. Initialize Ancestor Sets:
   • For each node, maintain a set to store its ancestors (using a set avoids duplicates).
3. Topological Traversal:
   • Start with all nodes that have indegree 0 (no incoming edges).
   • Process nodes in this order, and for each node, propagate its ancestor set (plus itself) to its neighbors.
   • Each time a neighbor's indegree drops to zero, add it to the processing queue.
4. Sort and Output:
   • Once all nodes are processed, convert each ancestor set to a sorted list for the final output.

This design ensures that each ancestor is computed only once per node, and we avoid redundant traversals by leveraging the DAG's properties and topological ordering.

Example Walkthrough

Suppose n = 4 and edges = [[0,1],[1,2],[2,3],[0,2]].

• Step 1: Build the graph:
  • 0 → [1,2]
  • 1 → [2]
  • 2 → [3]
  • 3 → []
  Indegree: [0,1,2,1]
• Step 2: Start with node 0 (indegree 0).
  • Process 0: Its neighbors are 1 and 2.
  • For 1: Ancestors = {0}
  • For 2: Ancestors = {0}
  • Update indegree: [0,0,1,1]
• Step 3: Next, process node 1 (now indegree 0).
  • Process 1: Neighbor is 2.
  • For 2: Ancestors = {0,1} (add 1 and all ancestors of 1)
  • Update indegree: [0,0,0,1]
• Step 4: Now process node 2.
  • Process 2: Neighbor is 3.
  • For 3: Ancestors = {0,1,2} (add 2 and all ancestors of 2)
  • Update indegree: [0,0,0,0]
• Step 5: Finally process node 3 (queue empty after).
• Final Output:
  • Node 0: []
  • Node 1: [0]
  • Node 2: [0,1]
  • Node 3: [0,1,2]

Time and Space Complexity

Brute-force approach: For each node, run a DFS or BFS to find all ancestors. This can be O(n(n+e)), where e is the number of edges, since each traversal could visit much of the graph.

Optimized/topological approach:

• Building the graph: O(e)
• Topological traversal: Each edge and node is processed once: O(n + e)
• Ancestor set updates: In the worst case, each ancestor set can grow to O(n) size, so total set operations are O(n^2) in the worst case.
• Total: O(n^2 + e) time and O(n^2) space (for storing all ancestor sets).

Summary

This problem leverages the properties of DAGs and topological order to efficiently compute all ancestors for each node. By propagating ancestor sets in topological order, we avoid redundant work and ensure each ancestor is only added once per node. The solution is both efficient and elegant, demonstrating the power of combining graph traversal strategies with set operations for problems involving reachability and ancestry in directed graphs.