LeetCode 2192 - All Ancestors of a Node in a Directed Acyclic Graph

This problem gives us a Directed Acyclic Graph (DAG) with n nodes labeled from 0 to n - 1, along with a list of directed edges. Each edge [u, v] means there is a one way connection from node u to node v. The goal is to compute, for every node i, all of its ancestors.

leetcodemediumdepth-first-searchbreadth-first-searchgraph-theorytopological-sort

LeetCode Problem 2192

Difficulty: 🟡 Medium
Topics: Depth-First Search, Breadth-First Search, Graph Theory, Topological Sort

Solution

Problem Understanding

This problem gives us a Directed Acyclic Graph (DAG) with n nodes labeled from 0 to n - 1, along with a list of directed edges. Each edge [u, v] means there is a one way connection from node u to node v.

The goal is to compute, for every node i, all of its ancestors.

An ancestor of a node v is any node u that can eventually reach v through one or more directed edges. Direct parent relationships are included, but so are indirect relationships through intermediate nodes.

For example, if:

0 -> 1 -> 2

Then:

  • 0 is an ancestor of 1
  • 1 is an ancestor of 2
  • 0 is also an ancestor of 2, because there exists a path 0 -> 1 -> 2

The required output is a list answer where:

answer[i]

contains every ancestor of node i, sorted in ascending order.

The important detail is that the graph is guaranteed to be a DAG, meaning there are no cycles. This guarantee matters because it allows us to process nodes in topological order, ensuring that when we process a node, all of its predecessors have already been handled.

Understanding the Constraints

The constraints are:

  • 1 <= n <= 1000
  • edges.length <= 2000

These limits are moderate. Since n is at most 1000, an O(n²) or even O(n³) solution may still be feasible in some cases, but we should aim for something more efficient.

A naive graph traversal from every node could work because the graph is relatively small, but we can do better by exploiting the DAG property.

The graph being acyclic is especially important because it means dependencies flow in one direction only, which makes topological sorting applicable.

Important Edge Cases

One important edge case is when there are no edges at all. In this case, every node has no ancestors, so the answer is simply a list of empty arrays.

Another edge case is a linear chain:

0 -> 1 -> 2 -> 3

In this case, ancestor lists grow progressively larger:

[[], [0], [0,1], [0,1,2]]

A third edge case is a graph with multiple incoming paths. If a node is reachable through different routes, we must avoid duplicate ancestors.

For example:

0 -> 2
1 -> 2
0 -> 1

Node 2 should contain [0,1], not duplicate 0.

The problem also guarantees:

  • No duplicate edges
  • No self loops
  • No cycles

These guarantees simplify implementation because we do not need cycle detection or duplicate edge filtering.

Approaches

Brute Force Approach

The brute force idea is straightforward: for every node u, run a graph traversal such as DFS or BFS to determine all nodes reachable from u.

Whenever node u reaches node v, we add u to v’s ancestor list.

In other words:

  1. Start DFS/BFS from every node.
  2. Visit all reachable descendants.
  3. Add the source node as an ancestor of each visited node.

This works because if u can reach v, then by definition u is an ancestor of v.

However, this approach becomes inefficient because we may repeatedly traverse overlapping parts of the graph.

For example, if many nodes share descendants, the same paths are explored multiple times.

Since we perform traversal for all n nodes, worst case complexity becomes:

O(n × (n + e))

where:

  • n = number of nodes
  • e = number of edges

Although this can pass for n = 1000, there is a cleaner DAG specific optimization.

Optimal Approach, Topological Sort + Ancestor Propagation

The key insight is that the graph is a DAG.

In a DAG, we can process nodes in topological order, meaning every node appears after all its prerequisites.

Suppose we know all ancestors of node u.

If there is an edge:

u -> v

Then every ancestor of u automatically becomes an ancestor of v.

Additionally, u itself becomes an ancestor of v.

So we can propagate ancestor information forward:

ancestors[v] =
ancestors[v] ∪ ancestors[u] ∪ {u}

We process nodes using Kahn’s Algorithm for topological sorting.

This guarantees that before processing a node, all incoming dependencies have already contributed their ancestor information.

Using sets helps avoid duplicates automatically.

Approach Time Complexity Space Complexity Notes
Brute Force O(n × (n + e)) O(n + e) Run DFS/BFS from every node
Optimal O(n² + e) O(n² + e) Topological sort with ancestor propagation

Algorithm Walkthrough

Step 1: Build the Graph

Create an adjacency list from the edge list.

For every edge:

u -> v

store v inside graph[u].

We also compute the indegree of each node, which counts how many incoming edges it has.

This information is required for topological sorting.

Step 2: Initialize Ancestor Storage

Create a list of sets:

ancestors[i]

Each set will eventually contain all ancestors of node i.

We use a set because:

  • duplicates must be avoided
  • insertion is efficient
  • union operations are easy

Step 3: Start Topological Sorting

Add all nodes with indegree 0 to a queue.

These nodes have no incoming edges, meaning they cannot have ancestors.

They act as starting points.

Step 4: Process Nodes in Topological Order

While the queue is not empty:

  1. Remove the current node u
  2. Visit each neighbor v
  3. Add u into ancestors[v]
  4. Merge all ancestors of u into ancestors[v]
  5. Decrease indegree of v
  6. If indegree becomes 0, push v into the queue

The propagation step is the most important:

ancestors[v].add(u)
ancestors[v].update(ancestors[u])

This transfers all known ancestor information forward.

Step 5: Convert Sets to Sorted Lists

The problem requires ancestors in ascending order.

Since sets are unordered, convert every set into a sorted list.

Return the final result.

Why it works

The correctness comes from topological ordering.

A node is processed only after all of its incoming dependencies have been processed. Therefore, when handling edge:

u -> v

the set ancestors[u] is already complete.

Adding:

ancestors[u] + {u}

to v guarantees that all valid ancestors are propagated exactly once.

Because every edge is processed and duplicates are removed by sets, the final ancestor lists are complete and correct.

Python Solution

from collections import deque
from typing import List

class Solution:
    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        graph = [[] for _ in range(n)]
        indegree = [0] * n

        for u, v in edges:
            graph[u].append(v)
            indegree[v] += 1

        ancestors = [set() for _ in range(n)]

        queue = deque()

        for node in range(n):
            if indegree[node] == 0:
                queue.append(node)

        while queue:
            current = queue.popleft()

            for neighbor in graph[current]:
                ancestors[neighbor].add(current)
                ancestors[neighbor].update(ancestors[current])

                indegree[neighbor] -= 1

                if indegree[neighbor] == 0:
                    queue.append(neighbor)

        return [sorted(list(ancestor_set)) for ancestor_set in ancestors]

Implementation Explanation

The solution begins by building the graph and indegree array. The adjacency list represents outgoing edges, while the indegree array tracks how many prerequisites each node has.

We then initialize an array of sets called ancestors. Each index stores all ancestors for a specific node.

A queue is initialized with nodes whose indegree equals zero. Since these nodes have no incoming edges, they have no ancestors and can be processed immediately.

During BFS traversal, each node propagates its ancestor information to neighbors.

For every neighbor:

ancestors[neighbor].add(current)

adds the direct parent.

Then:

ancestors[neighbor].update(ancestors[current])

adds all indirect ancestors.

After processing an edge, indegree is reduced. Once a node reaches indegree zero, all parent information has been processed, so it can safely enter the queue.

Finally, each set is sorted before returning because the problem requires ascending order.

Go Solution

func getAncestors(n int, edges [][]int) [][]int {
	graph := make([][]int, n)
	indegree := make([]int, n)

	for _, edge := range edges {
		u, v := edge[0], edge[1]
		graph[u] = append(graph[u], v)
		indegree[v]++
	}

	ancestors := make([]map[int]bool, n)

	for i := 0; i < n; i++ {
		ancestors[i] = make(map[int]bool)
	}

	queue := []int{}

	for i := 0; i < n; i++ {
		if indegree[i] == 0 {
			queue = append(queue, i)
		}
	}

	for len(queue) > 0 {
		current := queue[0]
		queue = queue[1:]

		for _, neighbor := range graph[current] {
			ancestors[neighbor][current] = true

			for ancestor := range ancestors[current] {
				ancestors[neighbor][ancestor] = true
			}

			indegree[neighbor]--

			if indegree[neighbor] == 0 {
				queue = append(queue, neighbor)
			}
		}
	}

	result := make([][]int, n)

	for i := 0; i < n; i++ {
		for ancestor := range ancestors[i] {
			result[i] = append(result[i], ancestor)
		}

		// sort ascending
		for j := 0; j < len(result[i]); j++ {
			for k := j + 1; k < len(result[i]); k++ {
				if result[i][j] > result[i][k] {
					result[i][j], result[i][k] =
						result[i][k], result[i][j]
				}
			}
		}
	}

	return result
}

Go Specific Notes

Go does not have a built in set type, so we simulate one using:

map[int]bool

This allows constant time insertion and automatic duplicate elimination.

Unlike Python, Go slices do not support popleft(), so queue operations are handled by slicing:

queue = queue[1:]

The Python version uses sorted(), while Go requires explicit sorting. In production code, sort.Ints(result[i]) would be preferred for readability and performance.

Nil handling is straightforward because each ancestor map is initialized before use.

Worked 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]]

Initial indegree:

Node Indegree
0 0
1 0
2 0
3 2
4 2
5 1
6 2
7 2

Initial queue:

[0,1,2]

Process Node 0

Updates:

0 -> 3
0 -> 4

Ancestors:

3 = {0}
4 = {0}

Queue:

[1,2]

Process Node 1

Update:

1 -> 3

Ancestors:

3 = {0,1}

Queue:

[2,3]

Process Node 2

Updates:

2 -> 4
2 -> 7

Ancestors:

4 = {0,2}
7 = {2}

Queue:

[3,4]

Process Node 3

Updates:

3 -> 5
3 -> 6
3 -> 7

Propagated ancestors:

5 = {0,1,3}
6 = {0,1,3}
7 = {0,1,2,3}

Process Node 4

Update:

4 -> 6

Now:

6 = {0,1,2,3,4}

Final answer:

[
 [], [], [],
 [0,1],
 [0,2],
 [0,1,3],
 [0,1,2,3,4],
 [0,1,2,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]]

Topological order:

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

Ancestor propagation:

Node Ancestors
0 {}
1 {0}
2 {0,1}
3 {0,1,2}
4 {0,1,2,3}

Final result:

[
 [],
 [0],
 [0,1],
 [0,1,2],
 [0,1,2,3]
]

Complexity Analysis

Measure Complexity Explanation
Time O(n² + e) Each edge is processed once, ancestor propagation may involve up to n ancestors
Space O(n² + e) Ancestor storage can grow to O(n²) in dense DAGs

The dominant cost comes from ancestor propagation. For each edge, we may merge a set containing up to n ancestors.

In the worst case, such as a chain graph:

0 -> 1 -> 2 -> ... -> n-1

ancestor sets grow progressively larger, producing an overall O(n²) cost.

Since n <= 1000, this complexity is efficient enough.

Test Cases

class Solution:
    def getAncestors(self, n, edges):
        from collections import deque

        graph = [[] for _ in range(n)]
        indegree = [0] * n

        for u, v in edges:
            graph[u].append(v)
            indegree[v] += 1

        ancestors = [set() for _ in range(n)]
        queue = deque(
            [i for i in range(n) if indegree[i] == 0]
        )

        while queue:
            current = queue.popleft()

            for neighbor in graph[current]:
                ancestors[neighbor].add(current)
                ancestors[neighbor].update(
                    ancestors[current]
                )

                indegree[neighbor] -= 1

                if indegree[neighbor] == 0:
                    queue.append(neighbor)

        return [sorted(a) for a in ancestors]

sol = Solution()

# Example 1
assert sol.getAncestors(
    8,
    [
        [0,3],[0,4],[1,3],[2,4],
        [2,7],[3,5],[3,6],[3,7],[4,6]
    ]
) == [
    [],[],[],
    [0,1],
    [0,2],
    [0,1,3],
    [0,1,2,3,4],
    [0,1,2,3]
]  # standard DAG example

# Example 2
assert sol.getAncestors(
    5,
    [
        [0,1],[0,2],[0,3],[0,4],
        [1,2],[1,3],[1,4],
        [2,3],[2,4],[3,4]
    ]
) == [
    [],
    [0],
    [0,1],
    [0,1,2],
    [0,1,2,3]
]  # dense DAG

# Single node
assert sol.getAncestors(
    1, []
) == [
    []
]  # minimum input

# No edges
assert sol.getAncestors(
    4, []
) == [
    [], [], [], []
]  # disconnected graph

# Linear chain
assert sol.getAncestors(
    4,
    [[0,1],[1,2],[2,3]]
) == [
    [],
    [0],
    [0,1],
    [0,1,2]
]  # ancestor accumulation

# Diamond graph
assert sol.getAncestors(
    4,
    [[0,1],[0,2],[1,3],[2,3]]
) == [
    [],
    [0],
    [0],
    [0,1,2]
]  # duplicate prevention

# Multiple roots
assert sol.getAncestors(
    5,
    [[0,3],[1,3],[2,4]]
) == [
    [],
    [],
    [],
    [0,1],
    [2]
]  # disconnected components
Test Why
Example 1 Validates standard DAG propagation
Example 2 Tests dense ancestor accumulation
Single node Minimum boundary case
No edges Ensures empty ancestor lists
Linear chain Tests transitive propagation
Diamond graph Verifies duplicate elimination
Multiple roots Validates disconnected components

Edge Cases

No Edges in the Graph

When the graph contains no edges, every node is isolated.

For example:

n = 4
edges = []

Every node has indegree zero and enters the queue immediately. Since there are no outgoing edges, no ancestor relationships are formed.

The implementation correctly returns:

[[], [], [], []]

Multiple Paths to the Same Node

A node may be reachable through multiple routes.

Example:

0 -> 1 -> 3
0 -> 2 -> 3

Without careful handling, ancestor 0 might be added twice.

The implementation avoids this bug by storing ancestors in a set, ensuring uniqueness automatically.

Long Dependency Chains

In a chain like:

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

each node accumulates all previous nodes as ancestors.

This stresses transitive propagation because every step inherits increasingly large ancestor sets.

The implementation handles this naturally through:

update(ancestors[current])

which propagates all indirect ancestors efficiently.

Disconnected Components

The graph may contain independent subgraphs.

Example:

0 -> 1

2 -> 3

Ancestor computation should stay isolated within each component.

Because topological processing begins from all indegree zero nodes simultaneously, disconnected components are handled correctly without any special logic.