Abstract / Summary

Find the smallest set of starting points so every node can be reached by 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 82% (200k+ submissions).

Typical patterns to solve this problem:

• Graph Theory

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 the minimal collection of vertices that must be selected so that every node in a directed graph becomes reachable. The core insight is that any vertex that has at least one incoming edge can be reached from another vertex, therefore only vertices with zero indegree need to be included in the answer. The method receives the total number of vertices n and a list of directed edges, then returns a list containing exactly those vertices that lack incoming edges.

Key Steps

Constructing the universal vertex set

all_vertices = set(range(n))

This line creates a set containing every vertex identifier from 0 up to n-1. Using a set provides constant-time membership checks and enables efficient set arithmetic later in the algorithm.

Extracting vertices that appear as destinations

destinations = { e[1] for e in edges }

A set comprehension iterates over each edge e and collects the second element, which represents the target vertex of the directed edge. Because a set automatically discards duplicates, multiple edges pointing to the same vertex do not inflate the collection.

Determining vertices without incoming edges

result = all_vertices - destinations

The set difference operation removes every vertex that appears in the destinations set from the universal set. The remaining elements are precisely those with no incoming edges. The method returns this set directly, which the caller can treat as a list of required source vertices.

Edge Cases Handled

When the graph contains no edges, the destinations set is empty, and the difference operation yields the full range of vertices. This correctly identifies that every vertex must be selected because none can be reached from another.

If n is zero, the range call produces an empty sequence, resulting in an empty all_vertices set. Subtracting any destinations (which must also be empty because there are no vertices) yields an empty result, matching the expectation for an empty graph.

Duplicate edges are collapsed by the set comprehension, so the algorithm does not waste effort counting the same incoming edge multiple times.

Self-loops, where an edge originates and terminates at the same vertex, cause that vertex to appear in the destinations set. Consequently, a vertex with only a self-loop is considered to have an incoming edge and is excluded from the final set, which aligns with the definition that it can be reached from itself.

Performance Optimizations

The solution leverages Python’s built-in set data structure for both storage and arithmetic. Set construction from a range and set comprehension are both implemented in C under the hood, providing fast execution. The use of a single set difference operation eliminates the need for explicit loops to filter vertices, reducing overhead. Because the algorithm processes each edge exactly once to build the destinations set and each vertex once to create the universal set, it scales linearly with the size of the input. The absence of auxiliary data structures beyond the two sets keeps memory usage minimal.

Overall, the implementation is concise, directly expresses the mathematical definition of the problem, and exploits Python’s efficient set operations to achieve optimal runtime behavior for the task at hand.

Imagine there is a huge playground with lots of colorful blocks scattered around. Some blocks have string connecting them to other blocks, like a giant spider web. These strings go in one direction, pointing from one block to another. The goal is to find which blocks are the starting points for all these paths.

If you look at the blocks, some have strings tied to them coming from other blocks. Those are not the starting points because something else leads to them. You want to find the special blocks that have absolutely no strings coming into them from anywhere. Since nobody is leading the way to these specific blocks, they must be the ones where the paths begin. The code looks at every single block in the playground, removes the ones that have strings pointing at them, and leaves behind only the ones that stand alone at the very start of the trails.

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

Time: linear
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					Go	Rust	TS
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	black-shadows	C++
	charles-wangkai			Java
	DimitrisJim							C
	everthis				JS
	fartem					Ruby
	FelixFan1122			Java
	fsq	C++
	JoshCrozier				JS
	keineahnung2345	C++
	lkwq007		Python
	suxrobGM						C#
	trung-hn		Python
	varunu28			Java
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
FelixFan1122	Java
fsq	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
suxrobGM	C#
trung-hn	Python
varunu28	Java
YuriSpiridonov	Python

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