All Ancestors of a Node in a Directed Acyclic Graph
Explanation & Solution
Description
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] = [from_i, to_i] denotes a unidirectional edge from node from_i to node to_i.
Return a list answer, where answer[i] is the list of ancestors of the i-th 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.
Examples
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]]
Explanation: Node 0 has no ancestors. Node 3 has ancestors 0 and 1. Node 5 has ancestors 0, 1, and 3 (since 0->3->5 and 1->3->5). Node 7 has ancestors 0, 1, 2, and 3.
Example 2
Input: n = 5, edges = [[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: This is a fully connected DAG. Each node i has all nodes 0 through i-1 as ancestors.
Constraints
- 1 <= n <= 1000
- 0 <= edges.length <= min(2000, n * (n - 1) / 2)
- edges[i].length == 2
- 0 <= from_i, to_i <= n - 1
- from_i != to_i
- There are no duplicate edges.
- The graph is a DAG (directed and acyclic).
Approach
Topological Sort pattern
1. Build the Graph
- Create an adjacency list from the directed edges.
- Compute the in-degree of each node.
2. Initialize Ancestor Sets
- Create an empty Set for each node to store its ancestors.
- Sets prevent duplicate entries and make union operations efficient.
3. Topological Sort with Ancestor Propagation
- Start BFS from all nodes with in-degree 0 (these have no ancestors).
- When processing a node, for each of its neighbors:
- Add the current node as an ancestor of the neighbor.
- Add all of the current node's ancestors to the neighbor's ancestor set.
- Decrement the neighbor's in-degree; if it reaches 0, add it to the queue.
4. Convert and Return
- Convert each ancestor Set to a sorted array in ascending order.
- Return the resulting list of lists.
Key Insight
- By processing nodes in topological order, we guarantee that when we visit a node, all of its ancestors have already been determined. This allows us to propagate the complete ancestor set forward through each edge, building up the full ancestor list for every node in a single pass.
Visualization
Press play to start bfs traversal