193. All Ancestors of a Node in a Directed Acyclic Graph
π LeetCode Problem: 2192. All Ancestors of a Node in a Directed Acyclic Graph
π Difficulty: Medium
π·οΈ Topics: Graph, DFS, BFS, Topological Sort, DAG
Problem Statement
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α΅’, toα΅’] denotes that there is a unidirectional edge from fromα΅’ to toα΅’ in the graph.
Return a list answer, where answer[i] is the list of ancestors of the iα΅Κ° 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, 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:
Graph visualization:
0 βββββ 3 βββββ 5
β β β
4 βββ 6 7 βββ 2
β β
βββββββββββββββ
Ancestors:
Node 0: [] (no incoming edges)
Node 1: [] (no incoming edges)
Node 2: [] (no incoming edges)
Node 3: [0,1] (0β3, 1β3)
Node 4: [0,2] (0β4, 2β4)
Node 5: [0,1,3] (can reach via 0β3β5, 1β3β5)
Node 6: [0,1,2,3,4] (multiple paths!)
Node 7: [0,1,2,3] (0β3β7, 1β3β7, 2β7)
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:
All nodes eventually lead to node 4.
Node 4 has ancestors from all other nodes!
Constraints:
- 1 <= n <= 1000
- 0 <= edges.length <= min(2000, n * (n - 1) / 2)
- edges[i].length == 2
- 0 <= fromα΅’, toα΅’ <= n - 1
- fromα΅’ != toα΅’
- There are no duplicate edges.
- The graph is directed and acyclic.
π³ Visual Understanding - The Complete Picture
The Problem We're Solving π€
Find ALL ancestors for each node in a DAG: π―
Example:
0 β 1 β 2
β β
3
Ancestors:
Node 0: [] (starting node)
Node 1: [0] (0 can reach 1)
Node 2: [0,1] (0β1β2, 1β2)
Node 3: [0,1,2] (0β1β3, 1β3, 2β3)
Question: For each node, who can reach it? π₯
Building Understanding Through Examples π
Example 1: Simple chain
Graph: 0 β 1 β 2 β 3
Ancestors:
Node 0: []
Node 1: [0]
Node 2: [0,1] (0β1β2, 1β2)
Node 3: [0,1,2] (0β1β2β3, 1β2β3, 2β3)
Pattern: Each node inherits all ancestors from parents!
Example 2: Diamond shape
Graph:
0
/ \
1 2
\ /
3
Ancestors:
Node 0: []
Node 1: [0]
Node 2: [0]
Node 3: [0,1,2] (paths: 0β1β3, 0β2β3, 0β3 implied)
Node 3 has ancestors from BOTH paths! π
Example 3: Complex DAG
Graph:
0 β 1 β 3
β β
2 β 4
Ancestors:
Node 0: []
Node 1: [0]
Node 2: [0]
Node 3: [0,1]
Node 4: [0,1,2] (0β2β4, 1β4, 0β1β4)
Multiple paths converge! Need to track all! π
Visual: Ancestor Propagation π
Start: 0 (ancestors: {})
β
Level 1: 1 (ancestors: {0})
β
Level 2: 2 (ancestors: {0,1})
β
Level 3: 3 (ancestors: {0,1,2})
Each node inherits parent's ancestors + parent itself! π
The Pattern Emerges π‘
Key observations: π
1οΈβ£ Transitive Reachability π―
If AβB and BβC, then A is ancestor of C
Ancestors propagate through edges!
2οΈβ£ DFS or BFS Works π
From each node, explore all reachable nodes
OR: For each node, find who can reach it
3οΈβ£ Topological Sort Order Helps β‘
Process nodes in topological order
Ancestors already computed for parents!
4οΈβ£ Need Deduplication π
Multiple paths to same node
Use Set to avoid duplicates
5οΈβ£ Two Approaches π οΈ
Approach 1: For each node, DFS to find reachable
Approach 2: Topological sort, propagate ancestors
π§ The Journey From Brute Force to Optimal
Part 1: Understanding the Problem - "Who can reach me?" π€
π The key question: For each node, who are its ancestors?
Ancestor = a node that can REACH this node through edges
Example:
Graph: 0 β 1 β 2
Node 0: Who can reach 0? Nobody! ancestors[0] = []
Node 1: Who can reach 1? Just 0! ancestors[1] = [0]
Node 2: Who can reach 2? 0 and 1! ancestors[2] = [0,1]
Two perspectives:
1. Forward: From each node, who can I reach? (descendants)
2. Backward: For each node, who can reach me? (ancestors)
Both work! Let's explore! π
Part 2: Approach 1 - "Reverse graph + DFS" π
π€ Simplest idea: Reverse the graph!
Original graph: A β B means "A is ancestor of B"
Reversed graph: B β A means "B can find A by following edges"
Algorithm:
1. Reverse all edges
2. For each node, DFS to find all reachable
3. Those reachable nodes = ancestors!
Example:
Original: 0 β 1 β 2
Reversed: 0 β 1 β 2
DFS from 0 (reversed): reaches nothing β []
DFS from 1 (reversed): reaches 0 β [0]
DFS from 2 (reversed): reaches 1, 0 β [0,1]
Perfect! Direct ancestor finding! β¨
Time: O(n Γ (V + E))
For each node: one DFS
Very intuitive! β
Part 3: Approach 2 - "BFS with topological sort" π‘
π€ Smarter approach: Use topological order!
Key insight:
Process nodes in topological order
When we process a node, all its parents already done!
Just inherit ancestors from parents!
Algorithm:
1. Topological sort (Kahn's BFS)
2. Process in order:
For each parent of current node:
Add all parent's ancestors to current
Add parent itself to current
Example:
Graph: 0 β 1 β 2
Topological order: [0, 1, 2]
Process 0: No parents β ancestors[0] = []
Process 1: Parent is 0
ancestors[1] = ancestors[0] + {0}
= {} + {0}
= {0} β
Process 2: Parent is 1
ancestors[2] = ancestors[1] + {1}
= {0} + {1}
= {0, 1} β
Elegant propagation! π
Time: O(V + E + total_ancestors)
Topological sort: O(V + E)
For each edge, copy ancestors
Often faster in practice! β‘
Part 4: Comparing Approaches π
π€ Which approach to use?
Approach 1: Reverse Graph + DFS
β
Very intuitive
β
Direct: "find who can reach me"
β
Simple to code
β Might revisit nodes multiple times
Time: O(n Γ (V + E))
Approach 2: Topological Sort + BFS Propagation
β
Each node processed once
β
Inherits from parents (elegant!)
β
Often faster in practice
β Slightly more complex logic
Time: O(V + E + total_ancestors)
Both correct! Both O(nΒ²) worst case!
For learning:
- Reverse DFS: Easier to understand β
- Topological BFS: More elegant π
We'll show both! π―
Part 5: The Pattern - "Ancestor propagation in DAG!" π―
β¨ This is about ANCESTOR PROPAGATION in DAG!
Key concepts:
β
Directed Acyclic Graph (DAG)
β
Transitive relationships (if AβBβC, then A ancestor of C)
β
Use topological order to propagate efficiently
Why topological sort helps:
Parents processed before children
Children can inherit all parent ancestors
No redundant computation!
This pattern applies to:
- Dependency chains
- Inheritance hierarchies
- Transitive closure computation
- Reachability queries
Two valid approaches:
1. Reverse + DFS: Intuitive, direct
2. Topo + BFS: Elegant, efficient
Both teach important graph concepts! π
π― Approach 1: Reverse Graph + DFS (Simplest!)
The Key Insight π‘
Reverse all edges then DFS from each node π. In reversed graph, following edges goes from descendants to ancestors π. DFS from node collects all its ancestors directly! π― Build reversed adjacency list ποΈ. For each node, DFS finds all reachable in reversed graph = all ancestors β¨. Use TreeSet for sorted order π. Time: O(nΓ(V+E)) β‘, Space: O(nΒ²) π¦!
Most intuitive approach! β
Complete Implementation
class Solution {
public List<List<Integer>> getAncestors(int n, int[][] edges) {
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
// REVERSE GRAPH + DFS APPROACH π
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
// Reverse edges: AβB becomes AβB
// DFS from each node finds its ancestors directly!
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
// BUILD REVERSED ADJACENCY LIST ποΈ
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
List<List<Integer>> reversedGraph = new ArrayList<>();
for (int i = 0; i < n; i++) {
reversedGraph.add(new ArrayList<>());
}
for (int[] edge : edges) {
int from = edge[0];
int to = edge[1];
// REVERSED: to β from
reversedGraph.get(to).add(from);
}
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
// FIND ANCESTORS FOR EACH NODE π
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
List<List<Integer>> result = new ArrayList<>();
for (int node = 0; node < n; node++) {
// βββββββββββββββββββββββββββββββββββββββββββββββ
// Use TreeSet for automatic sorting!
// βββββββββββββββββββββββββββββββββββββββββββββββ
Set<Integer> ancestors = new TreeSet<>();
boolean[] visited = new boolean[n];
// βββββββββββββββββββββββββββββββββββββββββββββββ
// DFS in reversed graph to find ancestors
// βββββββββββββββββββββββββββββββββββββββββββββββ
for (int parent : reversedGraph.get(node)) {
dfs(parent, reversedGraph, ancestors, visited);
}
result.add(new ArrayList<>(ancestors));
}
return result;
}
// βββββββββββββββββββββββββββββββββββββββββββββββββββββββ
// DFS IN REVERSED GRAPH π
// βββββββββββββββββββββββββββββββββββββββββββββββββββββββ
private void dfs(int node, List<List<Integer>> reversedGraph,
Set<Integer> ancestors, boolean[] visited) {
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
// Mark as visited and add to ancestors
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
visited[node] = true;
ancestors.add(node);
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
// Visit all neighbors (parents in original graph)
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
for (int parent : reversedGraph.get(node)) {
if (!visited[parent]) {
dfs(parent, reversedGraph, ancestors, visited);
}
}
}
}
Why This Works π―
Reversed edges invert relationships: π - Original: AβB means "A is ancestor of B" - Reversed: AβB means "follow backward to find A" - DFS backward = find all ancestors!
Direct ancestor collection: π― - Start from node's immediate parents - Recursively find their ancestors - Collect all reachable = all ancestors!
Visited prevents revisiting: β - Each ancestor visited once per DFS - Efficient exploration!
TreeSet gives sorted order: π - Automatic sorting as we add - No final sort needed!
π― Approach 2: BFS with Topological Sort (More Elegant!)
The Key Insight π‘
Use topological sort to process nodes in dependency order π. When processing a node, all parents already done β . Inherit ancestors from parents + add parents themselves! π Use Kahn's algorithm for topological order π. For each node, collect ancestors from all parents π₯. Elegant propagation! Time: O(V+E+total_ancestors) β‘, Space: O(nΒ²) π¦!
Clean and efficient! π
Complete Implementation
class Solution {
public List<List<Integer>> getAncestors(int n, int[][] edges) {
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
// TOPOLOGICAL SORT + ANCESTOR PROPAGATION π
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
// Process nodes in topological order
// Inherit ancestors from parents!
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
// BUILD ADJACENCY LIST ποΈ
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
int[] inDegree = new int[n];
for (int[] edge : edges) {
int from = edge[0];
int to = edge[1];
graph.get(from).add(to);
inDegree[to]++;
}
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
// INITIALIZE ANCESTOR SETS π
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
List<Set<Integer>> ancestorSets = new ArrayList<>();
for (int i = 0; i < n; i++) {
ancestorSets.add(new TreeSet<>());
}
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
// KAHN'S ALGORITHM - TOPOLOGICAL SORT π
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
Queue<Integer> queue = new LinkedList<>();
// Find nodes with no incoming edges
for (int i = 0; i < n; i++) {
if (inDegree[i] == 0) {
queue.offer(i);
}
}
while (!queue.isEmpty()) {
int current = queue.poll();
// βββββββββββββββββββββββββββββββββββββββββββββββ
// PROCESS CHILDREN: Inherit ancestors! π―
// βββββββββββββββββββββββββββββββββββββββββββββββ
for (int child : graph.get(current)) {
// βββββββββββββββββββββββββββββββββββββββββββ
// Child inherits all of current's ancestors
// βββββββββββββββββββββββββββββββββββββββββββ
ancestorSets.get(child).addAll(ancestorSets.get(current));
// βββββββββββββββββββββββββββββββββββββββββββ
// AND current itself is ancestor of child!
// βββββββββββββββββββββββββββββββββββββββββββ
ancestorSets.get(child).add(current);
// βββββββββββββββββββββββββββββββββββββββββββ
// Update in-degree
// βββββββββββββββββββββββββββββββββββββββββββ
inDegree[child]--;
if (inDegree[child] == 0) {
queue.offer(child);
}
}
}
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
// CONVERT SETS TO LISTS π
// βββββββββββββββββββββββββββββββββββββββββββββββββββ
List<List<Integer>> result = new ArrayList<>();
for (Set<Integer> ancestorSet : ancestorSets) {
result.add(new ArrayList<>(ancestorSet));
}
return result;
}
}
Why This Works π―
Topological order ensures parents first: π - Parents processed before children - Children can safely inherit from parents - No missing ancestors!
Inheritance propagation: π - child gets parent's ancestors - child gets parent itself - Transitive: if AβBβC, then C gets both A and B!
TreeSet maintains order: π - Sorted automatically - Handles duplicates (from multiple parents)
Kahn's algorithm guarantees order: β - Process zero in-degree first - Always correct topological order!
π Detailed Dry Run
Let's trace Approach 1 (Reverse Graph + DFS) on a small example:
n = 4
edges = [[0,1],[0,2],[1,3],[2,3]]
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β SETUP β
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Build REVERSED graph from edges:
Original [0,1]: 0β1 becomes Reversed: 1β0
Original [0,2]: 0β2 becomes Reversed: 2β0
Original [1,3]: 1β3 becomes Reversed: 3β1
Original [2,3]: 2β3 becomes Reversed: 3β2
Reversed adjacency list:
0: [] (no parents)
1: [0] (0 is parent)
2: [0] (0 is parent)
3: [1, 2] (1 and 2 are parents)
Original graph: Reversed graph:
0 0
/ \ β β
1 2 / \
\ / 1 2
3 β β
\ /
3
DFS for Each Node π
βββββββββββββββββββββββββββββββββββββββββββββββββββ
β π FIND ANCESTORS OF NODE 0 β
β ββββββββββββββββββββββββββββββββββββββββββββββββββ£
β Start from node 0's parents in reversed graph β
β β
β Parents of 0: [] (empty) β
β No parents to explore! β
β β
β ancestors[0] = {} β [] β
βββββββββββββββββββββββββββββββββββββββββββββββββββ
βββββββββββββββββββββββββββββββββββββββββββββββββββ
β π FIND ANCESTORS OF NODE 1 β
β ββββββββββββββββββββββββββββββββββββββββββββββββββ£
β Parents of 1: [0] β
β β
β ββββββββββββββββββββββββββββββββββββββββββββββββ
β DFS from parent 0: β
β ββββββββββββββββββββββββββββββββββββββββββββββββ
β visited[0] = true β
β Add 0 to ancestors β
β
β ancestors = {0} β
β β
β Parents of 0: [] (none) β
β Done! β
β β
β ancestors[1] = {0} β [0] β
βββββββββββββββββββββββββββββββββββββββββββββββββββ
βββββββββββββββββββββββββββββββββββββββββββββββββββ
β π FIND ANCESTORS OF NODE 2 β
β ββββββββββββββββββββββββββββββββββββββββββββββββββ£
β Parents of 2: [0] β
β β
β ββββββββββββββββββββββββββββββββββββββββββββββββ
β DFS from parent 0: β
β ββββββββββββββββββββββββββββββββββββββββββββββββ
β visited[0] = true β
β Add 0 to ancestors β
β
β ancestors = {0} β
β β
β Parents of 0: [] (none) β
β Done! β
β β
β ancestors[2] = {0} β [0] β
βββββββββββββββββββββββββββββββββββββββββββββββββββ
βββββββββββββββββββββββββββββββββββββββββββββββββββ
β π FIND ANCESTORS OF NODE 3 β
β ββββββββββββββββββββββββββββββββββββββββββββββββββ£
β Parents of 3: [1, 2] β
β β
β ββββββββββββββββββββββββββββββββββββββββββββββββ
β DFS from parent 1: β
β ββββββββββββββββββββββββββββββββββββββββββββββββ
β visited[1] = true β
β Add 1 to ancestors β
β
β ancestors = {1} β
β β
β Parents of 1: [0] β
β β
β DFS from 0: β
β visited[0] = true β
β Add 0 to ancestors β
β
β ancestors = {0, 1} β
β β
β Parents of 0: [] (none) β
β Done! β
β β
β ββββββββββββββββββββββββββββββββββββββββββββββββ
β DFS from parent 2: β
β ββββββββββββββββββββββββββββββββββββββββββββββββ
β visited[2] = true β
β Add 2 to ancestors β
β
β ancestors = {0, 1, 2} β
β β
β Parents of 2: [0] β
β β
β Try DFS from 0: β
β visited[0] = true (already!) β
β Skip! (already explored) β
β β
β ancestors[3] = {0, 1, 2} β [0, 1, 2] β
βββββββββββββββββββββββββββββββββββββββββββββββββββ
FINAL RESULT π
βββββββββββββββββββββββββββββββββββββββββββββββββ
β π FINAL RESULT: [[],[0],[0],[0,1,2]] β
β ββββββββββββββββββββββββββββββββββββββββββββββββ£
β β
β Verification: β
β Node 0: No incoming edges β
β
β Node 1: 0β1 β
β
β Node 2: 0β2 β
β
β Node 3: 0β1β3, 0β2β3 β
β
β All ancestors: {0, 1, 2} β
β
β β
β All paths correctly identified! π― β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββ
π Key Observations:
-
Reversed graph simplifies logic: π Following edges goes backward to ancestors
-
Direct ancestor finding: π― DFS from node directly finds its ancestors
-
Visited prevents re-exploration: β Node 0 visited once for node 3
-
TreeSet maintains order: π Ancestors automatically sorted
-
Much simpler than forward approach: β No need to track "who reaches whom"
π Complexity Analysis
Time Complexity: O(n Γ (V + E)) in worst case β‘
Where:
n = number of nodes
V = n (vertices)
E = number of edges
Analysis:
Approach 1 (Forward DFS):
For each node (n iterations):
DFS to find reachable nodes
DFS visits: O(V + E) per call
Total: O(n Γ (V + E))
But with optimization (Set.add() check):
If ancestor already added, prune DFS
In practice: much better than worst case!
Worst case: complete graph
Every node reaches every other node
O(n Γ (V + E)) β O(n Γ n) = O(nΒ²)
Approach 2 (Reverse DFS):
Same analysis: O(n Γ (V + E))
Convert to lists: O(total ancestors)
In worst case: O(nΒ²) ancestors total
Overall: O(nΒ²) worst case β‘
For sparse graphs: O(n Γ E) much better! π
Space Complexity: O(nΒ²) worst case π¦
Space usage:
1. Graph (adjacency list): O(V + E) ποΈ
n lists, total E edges
2. Ancestor sets: O(total ancestors) π
Worst case: complete DAG
Each node has O(n) ancestors
Total: O(nΒ²)
3. DFS recursion stack: O(V) π
Worst case: path of length n
O(n) depth
4. Result list: O(nΒ²) π
Same as ancestor sets
Total: O(E) + O(nΒ²) + O(n) + O(nΒ²) = O(nΒ²) π¦
Worst case dominates!
Example: n = 1000
Worst case: 1,000,000 ancestors total
Significant but manageable! β
π Related Problems & Patterns
Core Pattern: Reachability in DAG π―
// Template for finding all reachable nodes
class Solution {
// Forward DFS approach
public List<Set<Integer>> findReachable(int n, int[][] edges) {
List<List<Integer>> graph = buildGraph(n, edges);
List<Set<Integer>> reachable = new ArrayList<>();
for (int i = 0; i < n; i++) {
reachable.add(new TreeSet<>());
}
for (int start = 0; start < n; start++) {
dfs(start, start, graph, reachable);
}
return reachable;
}
private void dfs(int start, int current,
List<List<Integer>> graph,
List<Set<Integer>> reachable) {
for (int neighbor : graph.get(current)) {
if (reachable.get(neighbor).add(start)) {
dfs(start, neighbor, graph, reachable);
}
}
}
}
When to Use This Pattern π―
β
Find all ancestors/descendants in DAG
β
Transitive reachability queries
β
Build transitive closure
β
Dependency analysis
β
Path existence between all pairs
Recognition triggers: π - "All ancestors" or "all descendants" π₯ - Directed Acyclic Graph (DAG) π - Reachability queries π― - Transitive relationships π - Multiple paths to consider π
Key insight: DFS for transitive closure! π‘
Related LeetCode Problems π
Direct Applications:
-
Clone Graph (LC 133) - Medium π β’ What's similar: Graph traversal, DFS/BFS π β’ What's different: Clone structure, not find ancestors π β’ Key insight: DFS with visited tracking! π―
-
Course Schedule (LC 207) - Medium π β’ What's similar: DAG, dependencies π β’ What's different: Cycle detection, not ancestors β β’ Key insight: Topological sort! π
-
Evaluate Division (LC 399) - Medium β β’ What's similar: Graph reachability, paths π― β’ What's different: Weighted paths, ratios π β’ Key insight: DFS with path product! π‘
-
Network Delay Time (LC 743) - Medium β±οΈ β’ What's similar: Reachability, graph traversal π β’ What's different: Weighted edges, shortest paths β‘ β’ Key insight: Dijkstra's algorithm! π―
Pattern Evolution: π
Level 1: Basic Graph Traversal π
ββ Clone Graph (LC 133)
ββ Number of Islands (LC 200)
Level 2: DAG Reachability π― β HERE
ββ All Ancestors (LC 2192)
ββ Course Schedule (LC 207, 210)
ββ Topological Sort variations
Level 3: Advanced Reachability π
ββ Evaluate Division (LC 399)
ββ Network Delay Time (LC 743)
ββ Shortest Path algorithms
π Quick Revision Notes
π― Core Concept
All Ancestors finds all nodes that can reach each node in DAG using DFS from each node π. For each starting node, DFS explores all reachable descendants π―. Add starting node to ancestors of each reachable π. Use Set to prevent duplicates π. Set.add() returns false if already present β prune DFS! β‘ TreeSet maintains sorted order π. Alternative: reverse graph, DFS finds ancestors directly π. Time: O(nΒ²) worst case β‘, Space: O(nΒ²) π¦!
β‘ Quick Implementation (Reverse Graph - Simplest!)
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
import java.util.TreeSet;
public class Solution {
public List<List<Integer>> getAncestors(int n, int[][] edges) {
// return bfs(n, edges);
return dfs(n, edges);
}
private List<List<Integer>> dfs(int n, int[][] edges) {
List<List<Integer>> res = new ArrayList<>();
// Step 1: create graph
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
// GOTCHA: reverse edges while adding to graph which will
// be easy when we do DFS
for (int i = 0; i < edges.length; i++) {
graph.get(edges[i][1]).add(edges[i][0]);
}
// Step 2: do DFS for every node from 0 to n - 1
// For example, 0 -> 1 -> 2 becomes 0 <- 1 <- 2
// graph => {{1 : 0}, {2 : 1}}
// Also, keep track of visited, else no way of tracking visited nodes.
for (int node = 0; node < n; node++) {
// Ancestors of ith node
Set<Integer> ancestors = new TreeSet<>();
boolean[] visited = new boolean[n];
dfs(node, graph, ancestors, visited);
// in above example, for 0th node, it skips above
// loop and comes directly here.
res.add(new ArrayList<>(ancestors));
}
return res;
}
private void dfs(int node, List<List<Integer>> graph, Set<Integer> ancestors, boolean[] visited) {
for (int parent : graph.get(node)) {
if (visited[parent]) {
continue;
}
visited[parent] = true;
ancestors.add(parent);
dfs(parent, graph, ancestors, visited);
}
}
private List<List<Integer>> bfs(int n, int[][] edges) {
List<List<Integer>> res = new ArrayList<>();
// GOTCHA - extra to track ancestors. We can actually construct in res itself
// directly. Set is to just avoid duplicates edge cases.
List<Set<Integer>> ancestors = new ArrayList<>();
// Step 1: create graph and indegrees
List<List<Integer>> graph = new ArrayList<>();
int[] indegrees = new int[n];
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
indegrees[i] = 0;
// GOTCHA: this should be a treeset instead of hashset
// In question, its asked to return in the sorted order.
ancestors.add(new TreeSet<>());
}
for (int i = 0; i < edges.length; i++) {
graph.get(edges[i][0]).add(edges[i][1]); // directed graph
indegrees[edges[i][1]]++;
}
// Step 2: take 0 indegree elements
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (indegrees[i] == 0) {
queue.offer(i);
}
}
// Step 3: explore all queue (indegree) elements and add ancestors
while (!queue.isEmpty()) {
int curr = queue.poll();
for (int next : graph.get(curr)) {
// add parents of current parents
ancestors.get(next).addAll(ancestors.get(curr));
ancestors.get(next).add(curr); // add current parent
indegrees[next]--;
if (indegrees[next] == 0) {
queue.offer(next);
}
}
}
// Step 4: Convert to desired format.
for (Set<Integer> set : ancestors) {
res.add(new ArrayList<>(set));
}
return res;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.getAncestors(8,
new int[][] { { 0, 3 }, { 0, 4 }, { 1, 3 }, { 2, 4 }, { 2, 7 }, { 3, 5 }, { 3, 6 }, { 3, 7 }, { 4, 6 } }));
System.out.println(s.getAncestors(5, new int[][] { { 0, 1 }, { 0, 2 }, { 0, 3
}, { 0, 4 }, { 1, 2 }, { 1, 3 },
{ 1, 4 }, { 2, 3 }, { 2, 4 }, { 3, 4 } }));
}
}
π Key Insights
Reversed Graph Simplifies Logic: π
The KEY insight: Reverse edges!
Original graph:
0 β 1 β 2
"0 is ancestor of 1, 1 is ancestor of 2"
Reversed graph:
0 β 1 β 2
"Follow edges backward to find ancestors"
For node 2:
Start from 2
Follow backward: 2 β 1 β 0
Collect all reached: {0, 1} β
Why this works:
Original: "Who can I reach?" (descendants)
Reversed: "Who can reach me?" (ancestors)
Direct ancestor finding! π―
BFS Topological Approach: π
Alternative elegant approach:
Use topological sort (Kahn's algorithm)
Process nodes in dependency order
When processing node:
All parents already processed β
Inherit ancestors from parents!
Example:
0 β 1 β 2
Process 0: ancestors[0] = {}
Process 1:
Parent 0 processed β
ancestors[1] = ancestors[0] + {0}
= {} + {0} = {0}
Process 2:
Parent 1 processed β
ancestors[2] = ancestors[1] + {1}
= {0} + {1} = {0, 1}
Clean inheritance! π
Code:
for (int child : graph.get(current)) {
// Child inherits all of current's ancestors
ancestorSets.get(child).addAll(ancestorSets.get(current));
// Plus current itself!
ancestorSets.get(child).add(current);
}
Beautiful propagation! β¨
Why TreeSet? π
TreeSet automatically:
β
Keeps elements sorted
β
Prevents duplicates
β
No final sorting needed
Example:
Add in any order: 2, 0, 1
TreeSet: {0, 1, 2} β
Compare with ArrayList:
Add in any order: 2, 0, 1
List: [2, 0, 1]
Need to sort: Collections.sort() β
TreeSet is perfect! π―
Two Valid Approaches: βοΈ
Approach 1: Reverse Graph + DFS
β
Most intuitive
β
Direct ancestor finding
β
Simple to understand
Time: O(n Γ (V + E))
Approach 2: Topological + BFS
β
More elegant
β
Inheritan propagation
β
Each node processed once
Time: O(V + E + total_ancestors)
Both correct! Both O(nΒ²) worst case!
Choose based on preference! π―
πͺ Memory Aid
"DFS from each, to all we reach" π
"Add ourselves to those we teach" π
"Set returns false, stop we must" β‘
"Ancestors found, in Sets we trust" π β¨
β οΈ Don't Forget
- Use TreeSet - sorted order automatically! π
- Check Set.add() return - optimization! β‘
- DFS from each node - O(n) iterations! π
- Prune on false - avoid redundant exploration! π
- Convert Sets to Lists - final step! π
- Reverse approach works too - same complexity! π
You've mastered All Ancestors in DAG - reachability and transitive closure! ππ―β¨