Abstract / Summary

Given a directed acyclic graph and a node, find all nodes that have a path leading to this node.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 62% (200k+ submissions).

Typical patterns to solve this problem:

• Breadth First Search
• Depth First Search
• Graph Theory
• Topological Sort

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation computes, for every node in a directed acyclic graph (DAG) with n vertices, the list of all its ancestors. An ancestor of a node is any vertex from which there exists a directed path to that node. The algorithm builds a reverse adjacency structure, uses memoized depth-first recursion to collect ancestors, and finally assembles sorted ancestor lists for each vertex.

Building the reverse adjacency map

The first phase creates a dictionary that maps each node to the list of its direct predecessors. By storing edges in reverse order the later recursion can walk “upwards” from a node to its ancestors.

next = defaultdict(list)
for a, b in edges:
    next[b].append(a)   # reverse order

The defaultdict(list) automatically creates an empty list for a node that has no incoming edges, which simplifies later look-ups.

Recursive ancestor collection with memoization

A nested function deeper is defined and decorated with @cache. The function returns the set of all ancestors of a given node, including the node itself. The memoization ensures that each node’s ancestor set is computed only once, even if the node is reachable from many different descendants.

@cache
def deeper(node):
    result = set([node])
    for other in next[node]:
        result |= deeper(other)
    return result

The use of a set guarantees that duplicate ancestors are automatically eliminated during the union operation.

Aggregating ancestor sets for each vertex

An array parent of length n holds a set for each vertex. The algorithm iterates over the original edge list and, for each edge (a, b), merges the ancestor set of a (computed by deeper) into the set for b. Because deeper already includes a itself, the resulting set for b contains all ancestors of b.

parent = [set() for _ in range(n)]
for a, b in edges:
    parent[b] |= deeper(a)

Producing the final sorted output

The function returns a list where each entry corresponds to a vertex and contains its ancestors sorted in ascending order. Sorting is performed only once per vertex after all ancestors have been collected.

return [sorted(p) for p in parent]

Edge case handling

The code gracefully handles several edge conditions:

• Vertices with no incoming edges - For such nodes next[node] yields an empty list, so deeper returns a set containing only the node itself. Consequently, the corresponding entry in parent remains empty after the aggregation loop, and the final output for that vertex is an empty list.

• Disconnected components - Because the recursion is driven solely by the reverse adjacency map, each component is processed independently. The memoization cache isolates the computation per component, preventing cross-component interference.

• Multiple parents - When a node has several direct predecessors, the union operation result |= deeper(other) merges the ancestor sets from all parents. The set semantics automatically remove duplicates, ensuring each ancestor appears only once in the final list.

• Self-loops (if present) - The algorithm adds the node itself to its own ancestor set at the start of deeper. If a self-loop existed, the recursion would encounter the same node again, but the cached result would be returned immediately, avoiding infinite recursion.

Performance considerations

The implementation leverages two key optimizations:

• Memoization of recursive calls - By decorating deeper with @cache, the algorithm stores the computed ancestor set for each node after the first evaluation. Subsequent requests for the same node retrieve the cached set in constant time, eliminating redundant traversals of shared sub-paths in the DAG.

• Set union instead of repeated list concatenation - Using the |= operator on sets merges collections efficiently and maintains uniqueness without extra checks. This approach reduces the overhead associated with duplicate detection that would be required if lists were used.

The combination of a reverse adjacency map, memoized depth-first search, and set-based aggregation yields an algorithm that scales well with the size of the graph while keeping the code concise and readable.

Imagine a group of children playing a game where they hold hands to form a long family tree. Each child has a specific number, and the connections between them show who is an ancestor of whom.

The first part of the code gathers everyone and draws lines to show exactly who is connected to whom in reverse. It is like looking at a person and tracing the path back to find all the parents, grandparents, and those who came before them.

The special helper function called deeper acts like a detective. When it looks at a child, it goes back to see who that child’s parents were. Then it asks those parents about their own parents, and it keeps traveling backward until it finds every single ancestor for that person. Because there might be many ancestors, the code puts them all into a little collection to keep everything organized.

Once all the information is collected, the code looks at every child in the group. It uses the detective work started earlier to build a master list of ancestors for each person. Finally, it takes those lists of ancestors and puts them in order from the smallest number to the largest number so that everything is neat and easy to read.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java			TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java	C#	Go	TS
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fsq	C++
	JoshCrozier			JS
	lkwq007		Python
	shreymehul					C#
	suxrobGM					C#
	trung-hn		Python
	varunu28				Java
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
shreymehul	C#
suxrobGM	C#
trung-hn	Python
varunu28	Java
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality