Redundant Connection
Find the edge that creates a cycle in an almost-tree graph.
Pattern fit
This is union-find in its purest form: when two nodes already share the same root, the next edge is redundant.
Key observation
The first edge whose endpoints already connect is exactly the cycle-forming edge.
Target complexity
O(n alpha(n)) / O(n)
How to break down the solution cleanly
This is union-find in its purest form: when two nodes already share the same root, the next edge is redundant.
The first edge whose endpoints already connect is exactly the cycle-forming edge.
Initialize each node as its own parent.
Compress paths during find so future queries stay cheap.
Reference implementation
Python# Generic pattern template
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, a, b):
pa, pb = self.find(a), self.find(b)
if pa == pb:
return False
if self.rank[pa] < self.rank[pb]:
pa, pb = pb, pa
self.parent[pb] = pa
if self.rank[pa] == self.rank[pb]:
self.rank[pa] += 1
return True
Common pitfalls
Checking raw parent equality instead of roots.
Initializing DSU with the wrong node range.
Common follow-ups
Why is DSU simpler than DFS per edge here?
How would directed edges change the problem?
Continue with related problems
Build repeatable depth inside the Union Find cluster before moving on.