Redundant Connection
Find the one edge that turns a tree into a graph with a cycle, using union-find: the first edge whose two ends are already connected.
Problem Understanding
Redundant Connection: a tree on nodes 1..n had one extra edge added, giving n edges in all. Return an edge that can be removed so the result is a tree again. If there are several, return the one that appears last in edges.
Examples: [[1,2],[1,3],[2,3]] returns [2,3]; [[1,2],[2,3],[3,4],[1,4],[1,5]] returns [1,4].
The Intuition: Already Connected Means Redundant
Build the graph one edge at a time and keep track of which nodes are already connected:
- Each node starts alone. It is the root of its own set.
- An edge between two different sets is useful: it merges them, exactly as a tree edge would.
- An edge between two nodes in the same set adds nothing: they were already connected, so this edge closes a cycle. It is the answer.
The data structure that answers "same set?" and "merge" in near-constant time is union-find, also called a disjoint set. Graph Valid Tree asks the yes-or-no version of this question, and Min Cost to Connect All Points builds a minimum spanning tree, where the same "skip an edge whose ends are already connected" rule appears in Kruskal's algorithm. More problems like these are in the graphs pattern.
Interactive Walkthrough
GREEN = MERGED TWO SETS · RED = BOTH ENDS ALREADY JOINED
EACH NODE ALONE
edge
:
roots
:
answer
:
parent[i]
3 edges, so nodes 1 to 3. Each node starts as its own set: parent[i] = i
Next
Edge 1-2: find(1) = 1, find(2) = 2. Different roots, so merge the sets: parent[2] = 1
edges
Edges are handled in input order. A green edge merged two sets; the solid edge is the one being handled; a red edge had both ends in the same set already. The parent array is beside the graph, with the entries each step changed filled in. Try Path halving to watch find shorten a long chain as it climbs.
Dry Run Table
Input: [[1,2],[2,3],[3,4],[1,4],[1,5]]. parent starts as [1,2,3,4,5] for nodes 1 to 5.
| Edge | find(a) | find(b) | Action | parent (1..5) |
|---|---|---|---|---|
| 1-2 | 1 | 2 | parent[2] = 1 | 1 1 3 4 5 |
| 2-3 | 1 | 3 | parent[3] = 1 | 1 1 1 4 5 |
| 3-4 | 1 | 4 | parent[4] = 1 | 1 1 1 1 5 |
| 1-4 | 1 | 1 | same root: return | 1 1 1 1 5 |
Answer: [1,4]. The edge 1-5 is never reached.
The Solution Template
A parent array indexed 1 to n, a find with path halving, and one pass over the edges.
Redundant Connection Code
1var findRedundantConnection = function(edges) {2 const parent = Array.from({ length: edges.length + 1 }, (_, i) => i);3 const find = (x) => {4 while (parent[x] !== x) {5 parent[x] = parent[parent[x]];6 x = parent[x];7 }8 return x;9 };10 for (const [a, b] of edges) {11 const ra = find(a), rb = find(b);12 if (ra === rb) return [a, b];13 parent[rb] = ra;14 }15 return [];16};
Edge Cases & Common Mistakes
- 1-indexed nodes: size
parentasn + 1and ignore index 0. - Merging the nodes instead of the roots:
parent[b] = acan split a set; always link root to root,parent[rb] = ra. - Returning the wrong cycle edge: the problem wants the last one in the input. Processing in input order and returning the first edge with matching roots gives exactly that.
- Directed edges: Redundant Connection II (LeetCode 685) has directed edges and a node may get two parents; this solution does not handle that version.
- Recursion depth: a recursive
findwithout compression can recurse n deep on a long chain; the iterative loop avoids it.
Summary
Give each node its own set, then take the edges in order: if both ends already share a root, return that edge; otherwise link the roots. With path halving, O(n · α(n)) time and O(n) space.
More practice: DSA interview questions with answers · patterns cheat sheet