All Ancestors of a Node in a Directed Acyclic Graph

Given a DAG with n nodes and edges, for each node return all its ancestors (nodes that have a path to this node), sorted in ascending order.

Example 1

Input: n=8, edges=[[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]] → Output: [[],[],[],[0,1],[0,2],[0,1,3],[0,1,2,3,4],[0,1,2,3]]

Solution Approach

Topological sort then DP: for each node in topological order, its ancestors = union of ancestors of all its predecessors. Use BitSets for efficient set union.

Compute in-degrees. Topological sort (BFS/Kahn's).
For each node in topo order: for each neighbor, merge ancestor set.
Use List> or List for ancestors.
Collect results in sorted order.

Java

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<TreeSet<Integer>> anc = new ArrayList<>();
        for (int i = 0; i < n; i++) anc.add(new TreeSet<>());
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) if (inDegree[i] == 0) q.offer(i);
        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : graph.get(u)) {
                anc.get(v).add(u);
                anc.get(v).addAll(anc.get(u));
                if (--inDegree[v] == 0) q.offer(v);
            }
        }
        List<List<Integer>> res = new ArrayList<>();
        for (TreeSet<Integer> s : anc) res.add(new ArrayList<>(s));
        return res;
    }
}

Time Complexity: O(V * E) in worst case
Space Complexity: O(V^2)