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.
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]]
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.
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)