Abstract / Summary

A graph has one extra edge making it have a cycle and two nodes with two parents instead of one.

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 68% (900k+ submissions).

Typical patterns to solve this problem:

• Breadth First Search
• Depth First Search
• Graph Theory
• Union Find

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 solves the problem of detecting a redundant edge in an undirected graph that originally forms a tree. It employs a disjoint-set (union-find) data structure with path compression to maintain connectivity information while iterating through the edge list. When an edge connects two vertices that already belong to the same set, that edge is identified as the redundant one and returned immediately.

Key Steps

Initialization of the parent array

parent = [ i for i in range(len(edges) + 1) ]  # one-based indexing

A list named parent is created where each vertex is initially its own representative. The size is len(edges) + 1 because the vertices are numbered starting from 1, and there are exactly len(edges) edges in a tree plus one extra edge.

Find operation with path compression

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])  # path compression
    return parent[x]

The find function recursively climbs the parent chain until it reaches the root of the set. While unwinding the recursion, it flattens the structure by assigning each visited node directly to the root, which speeds up subsequent lookups.

Union operation that merges two sets

def union(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if x < y:
        parent[y] = x
    else:
        parent[x] = y

After locating the roots of the two vertices, the function attaches the larger root to the smaller one. This deterministic choice keeps the tree shallow without requiring an explicit rank or size array.

Edge processing loop

for a, b in edges:
    if find(a) == find(b):
        return (a, b)
    union(a, b)

The algorithm iterates over each edge. For each pair (a, b), it first checks whether the two vertices already share a common ancestor. If they do, the current edge would create a cycle and is therefore the redundant connection, which is returned as a tuple. If not, the edge is incorporated into the structure by uniting the two sets.

Edge Cases Handled

When the input graph contains exactly one extra edge beyond a spanning tree, the algorithm correctly identifies the first edge that would close a cycle. The use of one-based indexing ensures that vertices numbered from 1 up to n are addressed without off-by-one errors. The find function safely handles the case where a vertex is its own parent, returning the vertex itself without further recursion. The union function includes a guard (if x == y: return) that prevents unnecessary modifications when both vertices already belong to the same set, which could otherwise corrupt the parent relationships.

Performance Optimizations

Path compression inside the find function dramatically reduces the depth of the trees representing each set, turning future find calls into near-constant time operations. The deterministic choice of attaching the larger root to the smaller one (based on numeric comparison) provides a lightweight balancing heuristic without the overhead of maintaining explicit rank or size metadata. By returning immediately upon detecting a redundant edge, the algorithm avoids processing any remaining edges, which can save work in cases where the redundant edge appears early in the list. The overall design leverages in-place updates to the parent list, eliminating the need for auxiliary data structures and keeping memory usage minimal.

Imagine you have a bunch of dots on a piece of paper. Each edge in the list is like drawing a line between two of those dots. Some dots are already connected, and some are waiting for a turn.

The code starts by giving every dot its own little home. When a new line connects two dots, the code checks to see if they are already part of the same group. If they are already connected, it means the new line is extra because there is already a way to get from one dot to the other through different lines.

To keep track of everything, the code asks each dot to find the leader of its group. When two separate groups get a line between them, the code makes one leader join the other so all the dots become one big family. If the code ever finds two dots that already share the same leader before a line is even drawn, it knows that the current line is the one causing a loop.

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	JS			Go			TS
	LeetcodeHelp	C++	Python	Java
	Progiez	C++	Python	Java
github	black-shadows	C++
	charles-wangkai			Java
	DimitrisJim									C
	everthis				JS
	FelixFan1122			Java
	fengvyi	C++
	fpdjsns	C++
	halfrost							Go
	haoel		Python
	JoshCrozier				JS
	keineahnung2345	C++
	lkwq007		Python
	lzl124631x	C++
	MacJim	C++
	ruoru						Rust
	Shamik07								Dart
	shreymehul					C#
	sonugiri1043	C++
	suxrobGM					C#
	trung-hn		Python
	vthwang			Java
	wisdompeak	C++
	withaarzoo	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
FelixFan1122	Java
fengvyi	C++
fpdjsns	C++
halfrost	Go
haoel	Python
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
lzl124631x	C++
MacJim	C++
ruoru	Rust
Shamik07	Dart
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
vthwang	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