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] = [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.

Examples

Example 1:

 graph TD
     0 --> 3
     0 --> 4
     1 --> 3
     2 --> 4
     2 --> 7
     3 --> 5
     3 --> 6
     3 --> 7
     4 --> 6
  
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:

 graph TD;
     0
     1
     2
     1 --> 2
     1 --> 3
     1 --> 4
     2 --> 3
     2 --> 4
     0 --> 1
     0 --> 2
     0 --> 3
     0 --> 4
     3 --> 4
  
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.

Solution

Method 1 - DFS

Steps to follow:

  1. Build the graph with adjacency list representation
  2. Run the DFS on each node as parent, and see which nodes it can reach
  3. If the node is reachable, we add parent as to the ancestor list for that node

Here is the video explanation:

Code

Java
class Solution {

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

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

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

		List<List<Integer>> ans = new ArrayList<>();

		for (int i = 0; i < n; i++) {
			ans.add(new ArrayList<>());
		}
		
		for (int i = 0; i < n; i++) {
			dfs(graph, i, i, ans, new boolean[n]);
		}

		return ans;
	}

	public void dfs(List<List<Integer>> graph, int parent, int curr, List<List<Integer>> ans, boolean[] visited) {
		visited[curr] = true;

		for (int nei: graph.get(curr)) {
			if (!visited[nei]) {
				ans.get(nei).add(parent);
				dfs(graph, parent, nei, ans, visited);
			}
		}
	}
}

Complexity

  • ⏰ Time complexity: O(n * (n+m)) where n is number of nodes and m is number of edges. It takes O(n) time to initialize all adjacency lists, and O(m) time to fill in all adjacency list. So, O(n+m) for building the graph. For DFS from one node it takes O(n+m) time as well, but we are doing it for n nodes, hence O(n * (n+m)).
  • 🧺 Space complexity: O(n+m). O(n+m) for building graph, and O(n) for using visited set.

Method 2 - Topological Sorting using Kahns Algorithm BFS

We can optimize the given solution for finding the ancestors of nodes in a Directed Acyclic Graph (DAG) by using Depth-First Search (DFS) in combination with memoization to avoid redundant computations. Since the nodes are numbered from 0 to n-1, we can leverage the properties of the DAG and the topological order.

Approach

  1. Graph Construction: Builds the adjacency list representation of the graph and computes the in-degrees of each node.
  2. Topological Sort: Uses Kahn’s algorithm to perform a topological sort of the nodes. This helps us process each node before its descendants.
  3. Ancestors Calculation: Iterates through the nodes in topological order and populates the ancestor sets for each node. The ancestors of a node neighbor are the union of its immediate ancestor node and all ancestors of node. So, in a way it is DFS with memoization.
  4. Sorting: Converts the ancestor sets to lists and sorts them.

Code

Java
public class Solution {

	public List < List<Integer>> getAncestors(int n, int[][] edges) {
		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) {
			graph.get(edge[0]).add(edge[1]);
			inDegree[edge[1]]++;
		}

		// Topological sort using Kahn's Algorithm (BFS)
		Queue<Integer> queue = new LinkedList<>();

		for (int i = 0; i < n; i++) {
			if (inDegree[i] == 0) {
				queue.add(i);
			}
		}

		List<Integer> topologicalOrder = new ArrayList<>();

		while (!queue.isEmpty()) {
			int curr = queue.poll();
			topologicalOrder.add(curr);

			for (int neighbor: graph.get(curr)) {
				inDegree[neighbor]--;

				if (inDegree[neighbor] == 0) {
					queue.add(neighbor);
				}
			}
		}

		// List of ancestors for each node
		List<Set<Integer>> ancestors = new ArrayList<>();

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

		// Populate ancestors using topological order
		for (int node: topologicalOrder) {
			for (int neighbor: graph.get(node)) {
				ancestors.get(neighbor).add(node);
				ancestors.get(neighbor).addAll(ancestors.get(node));
			}
		}

		// Convert to sorted list
		List <List<Integer>> ans = new ArrayList<>();

		for (int i = 0; i < n; i++) {
			List<Integer> sortedAncestors = new ArrayList<>(ancestors.get(i));
			Collections.sort(sortedAncestors);
			ans.add(sortedAncestors);
		}

		return ans;
	}
}

Complexity

  • ⏰ Time complexity: O(n log n + m). For topological sorting it takes O(n+m), for ancestor collection it takes O(n) and for sorting it takes O(n log n)
  • 🧺 Space complexity: O(n + m) for storing the graph

Dry Run

We will take second graph for this, as it is smaller for debugging purposes.

n = 5, edgeList =[[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

 graph TD;
     0
     1
     2
     1 --> 2
     1 --> 3
     1 --> 4
     2 --> 3
     2 --> 4
     0 --> 1
     0 --> 2
     0 --> 3
     0 --> 4
     3 --> 4
Build the adjacency list

Adjacency list will be:

0 -> 1,2,3,4  
1 -> 2,3,4  
2 -> 3,4  
3 -> 4  
4 ->
Build In-degrees Vector
0 -> 0
1 -> 1
2 -> 2
3 -> 3
4 -> 4
Topological Sort

This is the code for that part:

// Topological sort using Kahn's Algorithm (BFS)
Queue<Integer> queue = new LinkedList<>();

for (int i = 0; i < n; i++) {
	if (inDegree[i] == 0) {
		queue.add(i);
	}
}

List<Integer> topologicalOrder = new ArrayList<>();

while (!queue.isEmpty()) {
	int curr = queue.poll();
	topologicalOrder.add(curr);

	for (int neighbor: graph.get(curr)) {
		inDegree[neighbor]--;

		if (inDegree[neighbor] == 0) {
			queue.add(neighbor);
		}
	}
}

Since, 0 is the only node with inDegree 0, we add to queue and start the BFS.

Now, the BFS starts.

Iteration 1

We pop out curr = 0, and start processing its neighbours - [1, 2, 3, 4]. We first reduce indegrees of neighbours, because we have processed their ancestor. Now, they are going to be next ancestor for processing.

Now, if any neighbours in-degree is now 0, we add it to the queue for processing. In this case, it will be 1. This is how the indegree will look now:

0 -> 0
1 -> 0
2 -> 1
3 -> 2
4 -> 3
Iteration 2

Now, we pop out curr = 1. We now process all its neighbours, i.e. [2, 3, 4]. We reduce their indegree by 1, add the one with indegree = 0 in the queue, i.e. 2.

This is how the indegree will look now:

0 -> 0
1 -> 0
2 -> 0
3 -> 1
4 -> 2
Finally

This will go and finally topological order will be [0, 1, 2, 3, 4].

Initialize and Populate ancestors
// List of ancestors for each node
List <Set<Integer>> ancestors = new ArrayList<>();

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

// Populate ancestors using topological order
for (int node: topologicalOrder) {
	for (int neighbor: graph.get(node)) {
		ancestors.get(neighbor).add(node);
		ancestors.get(neighbor).addAll(ancestors.get(node));
	}
}

This is the adjacency list and topological order:

0 -> 1,2,3,4  
1 -> 2,3,4  
2 -> 3,4  
3 -> 4  
4 ->


topologicalOrder = [0, 1, 2, 3, 4]
Iteration 1, node = 0

First node in list is node 0. So,

  • we will get all its neighbours, and add it as an ancestors to all its neighbours [1, 2, 3, 4]
  • Then, we will add all the ancestors of this ancestor to the list of all the ancestors.

Since node 0 has no ancestor, so only 0 wil be added as ancestor to its neighbours.

So, this is how ancestors look like:

0 -> [],
1 -> [0],
2 -> [0],
3 -> [0],
4 -> [0],
Iteration 2, node = 1

Now, we get node = 1. We will process its neighbours.

  • we will get all its neighbours, and add it as an ancestors to all its neighbours [2,3,4]
  • Then, we will add all the ancestors of this ancestor to the list of all the ancestors. Node 1 ancestor is node 0. If the ancestor is already added, we will just ignore it for addition. In this 0 is already present in the ancestor vector, for all the nodes.

This is how the ancestors will be build:

0 -> [],
1 -> [0],
2 -> [0, 1],
3 -> [0, 1],
4 -> [0, 1],
Finally

Resulting ancestors set:

0 -> [],
1 -> [0],
2 -> [0, 1],
3 -> [0, 1, 2],
4 -> [0, 1, 2, 3],
Convert to sorted list

We need the ancestors to be sorted as per the problem, so we sort them and add to answers, and this is how the answer now looks:

0 -> [],
1 -> [0],
2 -> [0, 1],
3 -> [0, 1, 2],
4 -> [0, 1, 2, 3],