Redundant Connection: Cycle Detection with Union-Find
Solve LeetCode Redundant Connection with Union-Find (DSU). Learn the cycle-detection insight, a worked trace, JavaScript code, and O(n·α(n)) complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
A tree with n nodes has exactly n - 1 edges. Add one more edge between two nodes that were already connected, and you've created exactly one cycle. Redundant Connection hands you that broken tree and asks: which edge is the extra one?
The naive instinct is to hunt for the cycle with a graph traversal. The sharper move is to never build the whole graph at all — process edges one at a time and catch the exact moment two already-connected nodes get wired together again. That's the Union-Find pattern, and it turns this problem into a near-linear scan.
The problem
You're given a graph that started as a tree with nodes labeled 1 to n, then had one extra edge added. The input is a list of edges, each [u, v] meaning an undirected connection between u and v. Return the one edge that can be removed so the result is still a tree. If multiple answers exist, return the edge that appears last in the input.
Input: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output: [1,4]
Nodes 1-2-3-4 form a square (a cycle). Node 5 hangs off node 1.
Both [3,4] and [1,4] sit on the cycle, but [1,4] comes later
in the list, so it is the redundant edge to remove.Two constraints do the heavy lifting. There is exactly one extra edge, so exactly one cycle exists. And "return the last one" means you should process edges in order and report the first one that closes a loop — because scanning front-to-back, the first cycle-closing edge you hit is the latest edge needed to complete that cycle.
The brute force baseline
The direct approach: after adding each edge, check whether the graph now contains a cycle. You can do that with a DFS from one endpoint, looking for a path back to the other.
function findRedundantConnection(edges) {
const adj = new Map();
for (const [u, v] of edges) {
// Does a path u -> v already exist without this edge?
if (adj.has(u) && adj.has(v) && hasPath(adj, u, v, new Set())) {
return [u, v];
}
if (!adj.has(u)) adj.set(u, []);
if (!adj.has(v)) adj.set(v, []);
adj.get(u).push(v);
adj.get(v).push(u);
}
return [];
}
function hasPath(adj, src, dst, seen) {
if (src === dst) return true;
seen.add(src);
for (const next of adj.get(src) || []) {
if (!seen.has(next) && hasPath(adj, next, dst, seen)) return true;
}
return false;
}This is correct, but each edge triggers a fresh DFS that can touch every node and edge already added. With n edges and an O(n) search per edge, you land at O(n²). The redundant work is obvious: you keep re-deriving connectivity you already knew. What you actually want is a structure that answers "are these two nodes already connected?" in near-constant time.
The key insight: track connectivity, not paths
Reframe the question. You don't care about the path between two nodes — only whether they already belong to the same connected group. That's a classic Disjoint Set Union (DSU, also called Union-Find) job.
DSU maintains a parent array where every node points toward a representative "root" for its group. Two operations run the show:
- find(x) — follow parent pointers up to the root that identifies x's group.
- union(u, v) — merge two groups by pointing one root at the other.
Now walk the edges. For each [u, v], look up both roots. If the roots differ, the edge joins two separate groups — safe, so union them. If the roots are the same, u and v were already connected, and this edge closes a cycle. That edge is the redundant one.
Because we process edges in input order, the first edge that finds a shared root is exactly the answer the problem wants: the last edge required to form the cycle.
The optimal solution
This mirrors the algorithm in the interactive visualizer, including path compression — the parent[node] = find(...) line that flattens the tree so future lookups are faster.
function findRedundantConnection(edges) {
const parent = [];
// Initialize DSU: a node's parent is initially itself
for (let i = 0; i <= edges.length; i++) {
parent.push(i);
}
// Find the absolute root of a given node
function find(node) {
if (parent[node] === node) return node;
// Path compression: point node straight at its root
return parent[node] = find(parent[node]);
}
// Union two components. Return false if already connected.
function union(u, v) {
const rootU = find(u);
const rootV = find(v);
if (rootU === rootV) return false; // cycle detected
parent[rootV] = rootU; // connect the trees
return true;
}
for (const [u, v] of edges) {
if (!union(u, v)) {
// u and v were already connected — this edge is redundant
return [u, v];
}
}
return [];
}The parent array is sized edges.length + 1 because nodes are labeled 1..n and n equals the edge count for this input shape. Index 0 is unused, which keeps the labels and array positions aligned so no off-by-one bookkeeping is needed.
Walkthrough
Trace edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]. Start with parent = [0,1,2,3,4,5], where every node is its own root.
| Edge | find(u) | find(v) | Same root? | Action | parent after |
|---|---|---|---|---|---|
| [1,2] | 1 | 2 | no | union → parent[2]=1 | [0,1,1,3,4,5] |
| [2,3] | 1 | 3 | no | union → parent[3]=1 | [0,1,1,1,4,5] |
| [3,4] | 1 | 4 | no | union → parent[4]=1 | [0,1,1,1,1,5] |
| [1,4] | 1 | 1 | yes | cycle → return [1,4] | — |
Row two is where path compression earns its keep: find(2) walks 2 → 1 and finds root 1, so nodes 2 and 3 merge under root 1. By the fourth edge, nodes 1, 2, 3, and 4 all share root 1. When [1,4] arrives, both endpoints resolve to root 1 — they're already in the same group, so this edge would form a cycle. The function returns [1,4] immediately and never even looks at [1,5].
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| DFS per edge | O(n²) | O(n) | each of n edges triggers an O(n) path search |
| Union-Find | O(n · α(n)) | O(n) | one union per edge; α(n) is the inverse Ackermann function |
With path compression, each find runs in amortized O(α(n)) time — the inverse Ackermann function, which stays below 5 for any input you'll ever see, so it's effectively constant. Across n edges the total is essentially linear. The space is the parent array, one slot per node.
Common mistakes
- Checking roots after the union. You must compare
rootUandrootVbefore merging. Merge first and every edge trivially shares a root, so cycle detection breaks entirely. - Sizing the parent array wrong. Labels run
1..n, so the array needsn + 1slots (index0unused). Sizing it tonthrows an out-of-bounds read on the highest-labeled node. - Returning the first edge on the cycle instead of the last. Front-to-back processing already gives the correct edge — the first one that closes the loop. Don't add extra logic to "find the earliest cycle edge"; that returns the wrong answer.
- Skipping path compression and assuming it's still fast. Without compression (and without union-by-rank), find can degrade to O(n) on a skewed chain, pushing the whole thing back toward O(n²). The one-line
parent[node] = find(...)is what keeps it near-linear.
Where this pattern shows up next
Union-Find and graph connectivity thinking carry straight into these problems:
- Shortest Path in Binary Matrix — grid connectivity solved with BFS instead of DSU.
- Network Delay Time — weighted graph traversal where you propagate signal times.
- Cheapest Flights Within K Stops — shortest path with a hop constraint.
- Find the City with Smallest Neighbors — all-pairs reachability under a distance threshold.
You can also step through Redundant Connection interactively to watch the DSU parent array collapse and the cycle-closing edge light up, one edge at a time.
FAQ
Why use Union-Find instead of DFS for Redundant Connection?
DFS after every edge re-searches connectivity you've already established, giving O(n²) time. Union-Find stores group membership directly in a parent array and answers "are these two nodes connected?" in near-constant amortized time. Processing all edges becomes an O(n · α(n)) scan — effectively linear — because each edge does one find-and-maybe-union instead of a fresh graph traversal.
How does Union-Find detect a cycle?
Before adding edge [u, v], you look up the root of each endpoint. If the roots differ, the nodes are in separate groups and the edge safely merges them. If the roots are identical, u and v were already reachable from each other, so this new edge creates a second path between them — a cycle. The edge that first produces two matching roots is the redundant one.
What is path compression and why does it matter?
Path compression is the parent[node] = find(parent[node]) trick: while resolving a node's root, you re-point that node directly at the root. Over time the tree flattens so future lookups are almost immediate. Combined across many operations, it drops the amortized cost of find to O(α(n)), the inverse Ackermann function, which is under 5 for all practical inputs. Without it, a degenerate chain of unions can make find linear and drag the whole algorithm back to O(n²).
Why does the parent array have n + 1 entries?
The nodes are labeled 1 through n, and this problem's input always has n edges, so edges.length equals n. Building parent with indices 0..n gives every node label a matching array slot and leaves index 0 unused. Aligning array positions with node labels avoids any offset math inside find and union, keeping the code clean and off-by-one bugs away.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.