Abstract / Summary

Find all nodes that will never enter a cycle when following directed edges.

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 71% (800k+ submissions).

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 determines all nodes in a directed graph that are eventually safe-nodes from which every possible path leads to a terminal node (a node with no outgoing edges). The algorithm proceeds by classifying nodes into two categories: safe nodes that are known to satisfy the condition, and loop nodes that belong to or can reach a cycle. It uses depth-first search with memoization to avoid redundant work.

Initialization

The algorithm begins by preparing two containers that will hold the classification results.

loop = set()
safe = set()

A first pass over the adjacency list identifies terminal nodes. Because a terminal node has no outgoing edges, it is trivially safe and is added to the safe set.

for i, next in enumerate(graph):
    if not next:
        safe.add(i)

Recursive Safety Check

The core of the solution is the nested function isSafe. It receives a node identifier n and a list seen that records the current recursion stack.

Loop Detection

If the current node appears in seen, a cycle has been discovered. All nodes on the current stack are marked as part of a loop, and the function reports that the node is not safe.

if n in seen:
    for s in seen:
        loop.add(s)
    return False

Memoized Results

Before exploring further, the function consults the memoization sets. A node already known to be in a loop is immediately rejected, while a node already known to be safe is accepted without further traversal.

if n in loop:
    return False
if n in safe:
    return True

Depth-First Exploration

When the node has not been classified yet, it is added to the recursion stack. The function then recursively checks each successor. If any successor is unsafe, the current node is added to the loop set and the search aborts for this branch.

seen.append(n)
for next in graph[n]:
    if not isSafe(next, seen.copy()):
        loop.add(n)
        return False

If all successors are safe, the node itself is recorded as safe.

safe.add(n)
return True

Traversal of All Nodes

After defining the helper, the algorithm iterates over every node in the graph, invoking isSafe with an empty stack. Nodes that return True are collected into the result list.

result = []
for i in range(len(graph)):
    if isSafe(i, []):
        result.append(i)

The final list is returned. Because nodes are examined in order of their indices and safe nodes are added only when confirmed, the result naturally appears sorted.

return result  # == sorted(safe)

Edge Cases Handled

The implementation explicitly treats nodes with no outgoing edges as safe during the initial pass, ensuring that isolated terminal nodes are correctly reported. Cycle detection works for self-loops as well as multi-node cycles because any re-encounter of a node in the current seen stack triggers the loop-marking logic. Nodes that are reachable from a cycle but not part of the cycle themselves are also classified as unsafe, because the recursive check propagates the failure upward.

Performance Optimizations

Memoization via the safe and loop sets prevents repeated exploration of subgraphs that have already been classified, turning what could be exponential recursion into a linear pass over each edge at most once for each classification. Early termination on the first unsafe successor reduces unnecessary work in dense graphs. The initial identification of terminal nodes populates the safe set before any recursion begins, allowing immediate acceptance of leaf nodes without invoking the recursive routine. The use of a set for membership checks provides constant-time lookups, contributing to the overall efficiency of the algorithm.

Imagine a big playground where every kid is holding a string that points to another kid they want to play with. Some kids are just hanging out by themselves, and others are chasing each other in a giant circle. If a kid is part of a circle, they can never stop running to catch the next person. If a kid is not in a circle, they will eventually stop and just stand still.

The computer looks at every kid one by one to see what happens. It starts by checking if a kid is already standing still. If the kid is pointing to other kids, the computer watches where those strings go. If the path leads into a circle, the computer remembers that everyone on that path is stuck running forever. If the path leads to a kid who is already standing still, then the computer knows that everyone on that path is safe.

The computer keeps a special list of all the kids who are part of a circle and a happy list of all the kids who are safe. As it explores the playground, it keeps track of who it has already visited so it does not get confused. Once the computer checks everyone, it looks at the safe list to see exactly which kids are allowed to stop running. Everyone left on that list is marked as safe.

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	JS	Java		Go
	LeetcodeHelp	C++	Python		Java
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fengvyi	C++
	halfrost						Go
	JoshCrozier			JS
	lkwq007		Python
	ruoru					Rust
	Shamik07							Dart
	suxrobGM								C#
	trung-hn		Python
	varunu28				Java
	wisdompeak	C++
	withaarzoo	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fengvyi	C++
halfrost	Go
JoshCrozier	JavaScript
lkwq007	Python
ruoru	Rust
Shamik07	Dart
suxrobGM	C#
trung-hn	Python
varunu28	Java
wisdompeak	C++
withaarzoo	C++
zfang399	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