All Ancestors of a Node in a Directed Acyclic Graph
MedPrompt
You are given a positive integer n representing the number of nodes of a Directed Acyclic Graph (DAG). The nodes are numbered from 0 to n - 1 (inclusive).
You are also given a 2D integer array edges, where edges[i] = [fromi, toi] denotes that there is a unidirectional edge from fromi to toi in the graph.
Return a list answer, where answer[i] is the list of ancestors of the ith node, sorted in ascending order.
A node u is an ancestor of another node v if u can reach v via a set of edges.
Example 1:
Input: n = 8, edgeList = [[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]]
Explanation:
The above diagram represents the input graph.
- Nodes 0, 1, and 2 do not have any ancestors.
- Node 3 has two ancestors 0 and 1.
- Node 4 has two ancestors 0 and 2.
- Node 5 has three ancestors 0, 1, and 3.
- Node 6 has five ancestors 0, 1, 2, 3, and 4.
- Node 7 has four ancestors 0, 1, 2, and 3.Example 2:
Input: n = 5, edgeList = [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Output: [[],[0],[0,1],[0,1,2],[0,1,2,3]]
Explanation:
The above diagram represents the input graph.
- Node 0 does not have any ancestor.
- Node 1 has one ancestor 0.
- Node 2 has two ancestors 0 and 1.
- Node 3 has three ancestors 0, 1, and 2.
- Node 4 has four ancestors 0, 1, 2, and 3.
Constraints:
1 <= n <= 10000 <= edges.length <= min(2000, n * (n - 1) / 2)edges[i].length == 20 <= fromi, toi <= n - 1fromi != toi- There are no duplicate edges.
- The graph is directed and acyclic.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach finds ancestors for each node independently. For any given node i, its ancestors are all nodes from which i is reachable. This is equivalent to finding all nodes that are reachable from i in a graph where all edge directions are reversed. We can run a separate graph traversal (like BFS or DFS) for each node on this reversed graph.
Algorithm
-
- Construct the reversed graph. Create an adjacency list
reversedAdjwhere ifu -> vis an edge in the original graph, we add an edgev -> u.
- Construct the reversed graph. Create an adjacency list
-
- Initialize a list of lists
ancestorsto store the results.
- Initialize a list of lists
-
- For each node
ifrom0ton-1:
- a. Perform a Breadth-First Search (BFS) starting from
ion thereversedAdj. - b. Use a
visitedarray to keep track of visited nodes to avoid redundant processing. - c. All nodes visited during this traversal are ancestors of
i. Collect them. - d. Sort the collected ancestors for node
iand add them to the final result list.
- For each node
Walkthrough
To find the ancestors of a specific node, say v, we need to identify all nodes u such that there exists a path from u to v. A more direct way to frame this is to reverse all the edges of the graph. In this reversed graph, a path from v to u signifies that u is an ancestor of v in the original graph.
This method iterates through each node i from 0 to n-1 and, for each one, performs a full graph traversal (BFS is used in the code below) starting from i on the reversed graph. All reachable nodes discovered during this traversal are the ancestors of i. After collecting all ancestors for a node, the list is sorted as required by the problem statement.
class Solution { public List<List<Integer>> getAncestors(int n, int[][] edges) { // Build a reversed adjacency list List<List<Integer>> revAdj = new ArrayList<>(); for (int i = 0; i < n; i++) { revAdj.add(new ArrayList<>()); } for (int[] edge : edges) { revAdj.get(edge[1]).add(edge[0]); } List<List<Integer>> ancestorsList = new ArrayList<>(); for (int i = 0; i < n; i++) { List<Integer> currentAncestors = new ArrayList<>(); boolean[] visited = new boolean[n]; Queue<Integer> queue = new LinkedList<>(); queue.add(i); visited[i] = true; // Mark start node as visited while (!queue.isEmpty()) { int u = queue.poll(); // Add to ancestors list only if it's not the start node if (u != i) { currentAncestors.add(u); } for (int v : revAdj.get(u)) { if (!visited[v]) { visited[v] = true; queue.add(v); } } } Collections.sort(currentAncestors); ancestorsList.add(currentAncestors); } return ancestorsList; }}To make the code slightly cleaner, we can run the BFS and collect all visited nodes, then sort and add them. The logic of not adding the start node i to its own ancestor list can be handled by starting the traversal from its parents in the reversed graph, or by simply filtering it out from the result of a traversal starting at i.
The BFS for each node explores a part of the graph. Since this is done for every node, many paths might be traversed multiple times, leading to inefficiency.
Complexity
Time
O(n * (n + m)), where n is the number of nodes and m is the number of edges. Building the reversed graph takes O(n + m). For each of the n nodes, we perform a traversal (BFS/DFS) which takes O(n + m) in the worst case. Sorting all ancestor lists takes an additional O(n^2 * log n) in the worst case, but this is dominated by the traversal complexity.
Space
O(n^2 + m). The reversed adjacency list takes O(n + m) space. The result list `ancestorsList` can store up to O(n^2) elements in total. The `visited` array and queue for BFS in each iteration take O(n) space.
Trade-offs
Pros
Conceptually simple and straightforward to implement.
Correctly solves the problem and is efficient enough for the given constraints.
Cons
Inefficient due to redundant computations. The reachability from an ancestor
ato a parentpof nodeiis re-calculated for every child ofp.
Solutions
Solution
public class Solution { private int n; private List < int > [] g; private IList < IList < int >> ans; public IList < IList < int >> GetAncestors(int n, int[][] edges) { g = new List < int > [n]; this.n = n; for (int i = 0; i < n; i++) { g[i] = new List < int > (); } foreach(var e in edges) { g[e[0]].Add(e[1]); } ans = new List < IList < int >> (); for (int i = 0; i < n; ++i) { ans.Add(new List < int > ()); } for (int i = 0; i < n; ++i) { BFS(i); } return ans; } private void BFS(int s) { Queue < int > q = new Queue < int > (); q.Enqueue(s); bool[] vis = new bool[n]; vis[s] = true; while (q.Count > 0) { int i = q.Dequeue(); foreach(int j in g[i]) { if (!vis[j]) { vis[j] = true; q.Enqueue(j); ans[j].Add(s); } } } }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.