1. 1-indexed nodes
Nodes are labeled 1..n, so size is edges.length + 1.
new UnionFind(edges.length + 1)Typorithm · medium
Redundant Connection
redundant-connectionunion-findcycle-edgemergeapplication
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Redundant Connection
Union-Find
Union each edge; the first edge whose union fails connects two already-joined nodes and is the redundant one.
A tree of n nodes has n - 1 edges; one extra edge creates exactly one cycle.
Unioning edges one by one, the redundant edge is the first whose endpoints already share a root.
When union returns false, both nodes were already connected, so this edge closes the cycle.
01
Extra edge forms one cycle.
02
union returning false flags it.
03
Return the first failing edge.
function findRedundantConnection(edges) {
const uf = new UnionFind(edges.length + 1);
for (const [a, b] of edges) {
if (!uf.union(a, b)) {
return [a, b];
}
}
return [];
}Read the implementation
Connect each part of the code to the concept before you type.
2. Union fails
A union that returns false means both endpoints already connect.
if (!uf.union(a, b)) {3. Cycle edge
That edge is the one closing a cycle.
return [a, b]A complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.