2192. All Ancestors of a Node in a DAG - Solution

The problem

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 that there is a unidirectional edge from from_i to to_i in the graph.

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.

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 <= 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 directed and acyclic.

Approach overview

Problem 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 1: DFS and Topological Sorting

This approach involves the following steps:

Create an adjacency list to represent the graph.
Perform topological sorting using a DFS to establish the processing order of each node.
For each node, use the established order to determine its ancestors by propagating the ancestors list from predecessors to successors in the order of DFS completion.
Finally, sort the ancestors list for each node as required in ascending order.

Python

from collections import defaultdict, deque

def getAncestors(n, edges):
    graph = defaultdict(list)
    indegree = [0] * n
    ancestors = [set() for _ in range(n)]

    # Build graph and calculate in-degrees
    for frm, to in edges:
        graph[frm].append(to)
        indegree[to] += 1

    # Topological Sort
    zero_indegree = deque()
    for i in range(n):
        if indegree[i] == 0:
            zero_indegree.append(i)

    while zero_indegree:
        node = zero_indegree.popleft()
        for neighbor in graph[node]:
            ancestors[neighbor].add(node)
            ancestors[neighbor].update(ancestors[node])
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                zero_indegree.append(neighbor)

    # Convert sets to sorted lists
    return [sorted(list(ancestor)) for ancestor in ancestors]

# Example usage
n = 8
edges = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]
print(getAncestors(n, edges))

Java

import java.util.*;

public class Ancestors {
    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        int[] indegree = new int[n];
        List<Set<Integer>> ancestors = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
            ancestors.add(new TreeSet<>());
        }

        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            indegree[edge[1]]++;
        }

        Queue<Integer> zeroIndegree = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                zeroIndegree.add(i);
            }
        }

        while (!zeroIndegree.isEmpty()) {
            int node = zeroIndegree.poll();
            for (int neighbor : graph.get(node)) {
                ancestors.get(neighbor).add(node);
                ancestors.get(neighbor).addAll(ancestors.get(node));
                if (--indegree[neighbor] == 0) {
                    zeroIndegree.add(neighbor);
                }
            }
        }

        List<List<Integer>> result = new ArrayList<>();
        for (Set<Integer> ancestorSet : ancestors) {
            result.add(new ArrayList<>(ancestorSet));
        }

        return result;
    }
    // Example usage
    // public static void main(String[] args) {
    //     Ancestors sol = new Ancestors();
    //     int n = 8;
    //     int[][] edges = {{0,3},{0,4},{1,3},{2,4},{2,7},{3,5},{3,6},{3,7},{4,6}};
    //     List<List<Integer>> result = sol.getAncestors(n, edges);
    //     // Output result
    // }
}

C++

#include <vector>
#include <queue>
#include <set>
using namespace std;

vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
    vector<vector<int>> graph(n);
    vector<int> indegree(n, 0);
    vector<set<int>> ancestors(n);

    for (const auto& edge : edges) {
        graph[edge[0]].push_back(edge[1]);
        indegree[edge[1]]++;
    }

    queue<int> zero_indegree;
    for (int i = 0; i < n; ++i) {
        if (indegree[i] == 0) {
            zero_indegree.push(i);
        }
    }

    while (!zero_indegree.empty()) {
        int node = zero_indegree.front();
        zero_indegree.pop();
        for (int neighbor : graph[node]) {
            ancestors[neighbor].insert(node);
            ancestors[neighbor].insert(ancestors[node].begin(), ancestors[node].end());
            if (--indegree[neighbor] == 0) {
                zero_indegree.push(neighbor);
            }
        }
    }

    vector<vector<int>> result(n);
    for (int i = 0; i < n; ++i) {
        result[i] = vector<int>(ancestors[i].begin(), ancestors[i].end());
    }
    return result;
}

// Example usage
// int main() {
//     int n = 8;
//     vector<vector<int>> edges = {{0,3},{0,4},{1,3},{2,4},{2,7},{3,5},{3,6},{3,7},{4,6}};
//     vector<vector<int>> result = getAncestors(n, edges);
//     // Output result
// }

This solution uses a DFS-based topological sort to process each node in a DAG. We represent the graph as an adjacency list and maintain an indegree count. Nodes with no incoming edges are processed first, during which their ancestors are propagated to their children nodes. This is done until all nodes are processed, yielding a set of ancestors which we then convert to a sorted list for each node to meet the problem requirement.

Complexity

Time Complexity: O(V + E), where V is the number of nodes and E is the number of edges, since we're effectively traversing all nodes and edges.
Space Complexity: O(V + E), due to the storage needed for the graph representation and the ancestors lists.

Try this approach in the editor

Approach 2: Reverse Edge DFS

Here, we reverse the edges in the graph and then perform a DFS for each node to find all reachable nodes, which now represent ancestors. This is an implementation that directly finds ancestors by traversing upwards in the graph via reversed edges:

Create an adjacency list but with reversed edges.
For each node, perform DFS to locate all nodes that can reach it (which are ancestors in the original graph).
Cautiously compile and sort results before returning, ensuring a time-efficient DFS exploration by marking visited nodes.

Python

from collections import defaultdict

def getAncestors(n, edges):
    reverse_graph = defaultdict(list)
    ancestors = [[] for _ in range(n)]

    # Build graph but reversed
    for frm, to in edges:
        reverse_graph[to].append(frm)

    def dfs(node, seen):
        for parent in reverse_graph[node]:
            if parent not in seen:
                ancestors[node].append(parent)
                seen.add(parent)
                dfs(parent, seen)

    for i in range(n):
        seen = set()
        dfs(i, seen)
        ancestors[i].sort()

    return ancestors

# Example usage
n = 8
edges = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]
print(getAncestors(n, edges))

Java

import java.util.*;

public class AncestorsReverseDFS {
    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        List<List<Integer>> reverseGraph = new ArrayList<>();
        List<Set<Integer>> ancestors = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            reverseGraph.add(new ArrayList<>());
            ancestors.add(new HashSet<>());
        }

        for (int[] edge : edges) {
            reverseGraph.get(edge[1]).add(edge[0]);
        }

        for (int i = 0; i < n; i++) {
            boolean[] visited = new boolean[n];
            dfs(i, reverseGraph, ancestors, visited);
        }

        List<List<Integer>> result = new ArrayList<>();
        for (Set<Integer> ancestorSet : ancestors) {
            List<Integer> list = new ArrayList<>(ancestorSet);
            Collections.sort(list);
            result.add(list);
        }

        return result;
    }

    private void dfs(int node, List<List<Integer>> reverseGraph, List<Set<Integer>> ancestors, boolean[] visited) {
        visited[node] = true;
        for (int parent : reverseGraph.get(node)) {
            if (!visited[parent]) {
                dfs(parent, reverseGraph, ancestors, visited);
            }
            ancestors.get(node).add(parent);
            ancestors.get(node).addAll(ancestors.get(parent));
        }
    }

    // Example usage
    // public static void main(String[] args) {
    //     AncestorsReverseDFS sol = new AncestorsReverseDFS();
    //     int n = 8;
    //     int[][] edges = {{0,3},{0,4},{1,3},{2,4},{2,7},{3,5},{3,6},{3,7},{4,6}};
    //     List<List<Integer>> result = sol.getAncestors(n, edges);
    //     // Output result
    // }
}

C++

#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;

void dfs(int node, vector<vector<int>>& reverseGraph, vector<unordered_set<int>>& ancestors, vector<bool>& visited) {
    visited[node] = true;
    for (int parent : reverseGraph[node]) {
        if (!visited[parent]) {
            dfs(parent, reverseGraph, ancestors, visited);
        }
        ancestors[node].insert(parent);
        ancestors[node].insert(ancestors[parent].begin(), ancestors[parent].end());
    }
}

vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
    vector<vector<int>> reverseGraph(n);
    vector<unordered_set<int>> ancestors(n);

    for (const auto& edge : edges) {
        reverseGraph[edge[1]].push_back(edge[0]);
    }

    for (int i = 0; i < n; ++i) {
        vector<bool> visited(n, false);
        dfs(i, reverseGraph, ancestors, visited);
    }

    vector<vector<int>> result(n);
    for (int i = 0; i < n; ++i) {
        result[i] = vector<int>(ancestors[i].begin(), ancestors[i].end());
        sort(result[i].begin(), result[i].end());
    }
    return result;
}

// Example usage
// int main() {
//     int n = 8;
//     vector<vector<int>> edges = {{0,3},{0,4},{1,3},{2,4},{2,7},{3,5},{3,6},{3,7},{4,6}};
//     vector<vector<int>> result = getAncestors(n, edges);
//     // Output result
// }

This solution reverses the direction of edges and applies DFS for each node to find reachable nodes (representing ancestors). Each DFS invocation tracks visited nodes to prevent reprocessing and adds ancestors directly to the current node's list, which is then sorted for output.

Complexity

Time Complexity: O(V * (V + E)), due to performing DFS from every node and having potential to traverse the full graph per DFS call.
Space Complexity: O(V + E), where V storage comes from graph information and visited nodes tracking.

Try this approach in the editor

Approach 3: BFS

First, we construct the adjacency list g based on the two-dimensional array edges, where g[i] represents all successor nodes of node i.

Then, we enumerate node i as the ancestor node from small to large, use BFS to search all successor nodes of node i, and add node i to the ancestor list of these successor nodes.

The time complexity is O(n^2), and the space complexity is O(n^2). Where n is the number of nodes.

TypeScript

function getAncestors(n: number, edges: number[][]): number[][] {
    const g: number[][] = Array.from({ length: n }, () => []);
    for (const [u, v] of edges) {
        g[u].push(v);
    }
    const ans: number[][] = Array.from({ length: n }, () => []);
    const bfs = (s: number) => {
        const q: number[] = [s];
        const vis: boolean[] = Array.from({ length: n }, () => false);
        vis[s] = true;
        while (q.length) {
            const i = q.pop()!;
            for (const j of g[i]) {
                if (!vis[j]) {
                    vis[j] = true;
                    ans[j].push(s);
                    q.push(j);
                }
            }
        }
    };
    for (let i = 0; i < n; ++i) {
        bfs(i);
    }
    return ans;
}

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);
                }
            }
        }
    }
}

func getAncestors(n int, edges [][]int) [][]int {
	g := make([][]int, n)
	for _, e := range edges {
		g[e[0]] = append(g[e[0]], e[1])
	}
	ans := make([][]int, n)
	bfs := func(s int) {
		q := []int{s}
		vis := make([]bool, n)
		vis[s] = true
		for len(q) > 0 {
			i := q[0]
			q = q[1:]
			for _, j := range g[i] {
				if !vis[j] {
					vis[j] = true
					q = append(q, j)
					ans[j] = append(ans[j], s)
				}
			}
		}
	}
	for i := 0; i < n; i++ {
		bfs(i)
	}
	return ans
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
DFS and Topological Sorting	Time Complexity: O(V + E), where V is the number of nodes and E is the number of edges, since we're effectively traversing all nodes and edges. Space Complexity: O(V + E), due to the storage needed for the graph representation and the ancestors lists.
Reverse Edge DFS	Time Complexity: O(V * (V + E)), due to performing DFS from every node and having potential to traverse the full graph per DFS call. Space Complexity: O(V + E), where V storage comes from graph information and visited nodes tracking.
BFS	–

Complexity analysis

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

Frequently asked questions

Is All Ancestors of a Node in a Directed Acyclic Graph easy or hard?

The problem is classified as Medium on LeetCode. The challenge comes from understanding how to propagate ancestor information across a DAG efficiently. Familiarity with graph traversal, DFS/BFS, and topological sorting makes the solution straightforward.

All Ancestors of a Node in a Directed Acyclic Graph Python/Java solution

Python, Java, and C++ implementations typically build an adjacency list and either run topological sort with ancestor propagation or perform DFS on a reversed graph. Both approaches track visited nodes and collect ancestor sets which are sorted before returning the final result.

How to solve All Ancestors of a Node in a Directed Acyclic Graph in O(n*(n+m))?

Build an adjacency list and compute a topological ordering of the DAG. Maintain a set or list of ancestors for every node. When processing an edge u -> v, insert u into v's ancestor set and merge all ancestors of u into v. Continue this propagation along the topological order so every node receives the full ancestor list.

What is the best approach for All Ancestors of a Node in a Directed Acyclic Graph?

Topological sort with ancestor propagation is the most efficient and commonly expected solution. Process nodes in topological order and propagate ancestor sets along outgoing edges. Each node accumulates its parents and their ancestors. The time complexity is O(n*(n+m)) with O(n^2) space for storing ancestor lists.

Is All Ancestors of a Node in a Directed Acyclic Graph asked at Google/Amazon/Meta?

Graph traversal and DAG ancestor problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variations involve dependency graphs, prerequisite tracking, or propagating information through a DAG using topological sort or DFS.

What data structure is used in All Ancestors of a Node in a Directed Acyclic Graph?

The solution uses an adjacency list to represent the directed graph and a set or list for storing ancestors of each node. Algorithms typically rely on depth-first search (DFS), breadth-first search (BFS), or topological sorting with a queue for nodes with zero indegree.

What is the time complexity of All Ancestors of a Node in a Directed Acyclic Graph?

Most optimal implementations run in O(n*(n+m)) time where n is the number of nodes and m is the number of edges. Topological propagation may merge ancestor sets during traversal, while reverse DFS performs a traversal for each node. Space complexity can reach O(n^2) because each node may have up to n ancestors.

All Ancestors of a Node in a Directed Acyclic Graph solution and explanation

The problem

Approach overview

Approach 1: DFS and Topological Sorting

Approach 2: Reverse Edge DFS

Approach 3: BFS

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

All Ancestors of a Node in a Directed Acyclic Graph solution and explanation

The problem

Approach overview

Approach 1: DFS and Topological Sorting

Approach 2: Reverse Edge DFS

Approach 3: BFS

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems