Watch 10 video solutions for All Ancestors of a Node in a Directed Acyclic Graph, a medium level problem involving Depth-First Search, Breadth-First Search, Graph. This walkthrough by codestorywithMIK has 9,136 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 != toiProblem Overview: You are given a directed acyclic graph (DAG) with n nodes and edges [u, v]. For every node v, compute all nodes that can reach v. The result must list ancestors for each node in sorted order.
Approach 1: DFS with Topological Sorting (O(n*(n+m)) time, O(n^2) space)
This approach processes the DAG in topological order so every node is visited only after its prerequisites. Build an adjacency list and compute a topological order using topological sort. Maintain a set of ancestors for each node. When processing an edge u -> v, add u to v's ancestor set and union all ancestors of u into v. Because the graph is acyclic, ancestors propagate forward without needing revisits. This method leverages the dependency ordering of DAGs and works well when you already compute topological order.
Approach 2: Reverse Edge DFS (O(n*(n+m)) time, O(n+m) space)
Instead of propagating ancestors forward, flip the edges and search backward. Build a reversed adjacency list where v -> u means u is a parent of v. For every node i, run a depth-first search or breadth-first search on the reversed graph to find all reachable nodes. Those reachable nodes are exactly the ancestors of i. Track visited nodes to avoid cycles (even though DAG guarantees none) and collect results. This approach is conceptually simpler because each search directly discovers the ancestor set for one node.
Recommended for interviews: The topological propagation approach is typically preferred. It demonstrates understanding of DAG processing and avoids repeating full traversals for each node. Reverse DFS still works and is easier to reason about, but interviewers usually expect a solution that leverages topological ordering to propagate ancestor information efficiently across the graph.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS with Topological Sort | O(n*(n+m)) | O(n^2) | Best general approach for DAG problems where information propagates along edges |
| Reverse Edge DFS | O(n*(n+m)) | O(n+m) | Simpler logic when computing ancestors independently for each node |