DSA AnimatorDSA animations
Redundant Connection LC #684 Medium Union-Find
Problem

A tree with n nodes (labelled 1..n) had one extra edge added. Given the list of edges, return an edge that can be removed so the graph becomes a tree again. If there are several answers, return the one that appears last in the input.

Example 1
Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]
Example 2
Input: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output: [1,4]
Constraints: n == edges.length  |  3 โ‰ค n โ‰ค 1000  |  no repeated edges  |  the graph is connected
๐Ÿ”— Edges
๐ŸŒ Graph (edges added so far)
๐ŸŒณ Union-Find forest (arrow โ†’ parent, ๐Ÿ‘‘ = root)
find(u) path find(v) path parent just changed ๐Ÿ‘‘ root ยท r = rank๐Ÿšจ edge inside one group = cycle
Variables
edge
โ€”
find(u)
โ€”
find(v)
โ€”
groups
โ€”
๐Ÿ’ก Step Logic
Press โ–ถ Play or Next to begin.
โœ“
Ready
0 / 0
Pick an example and press Play.
Algorithm
1
Every node starts as its own group: parent[i] = i ๐Ÿ‘‘
2
For edge (u, v): find both roots, flattening the path on the way
3
Same root โ†’ they're already connected โ†’ return this edge ๐Ÿšจ
4
Different roots โ†’ union: hang the lower-rank root under the higher-rank one
Time
O(n ยท ฮฑ(n))
Space
O(n)
๐Ÿง  Why these two tricks?

Path compression points every node on a find path straight at the root, so the next find is one hop. Union by rank always hangs the shorter tree under the taller one, so trees stay flat. Together, each operation costs about ฮฑ(n), the inverse Ackermann function, which is โ‰ค 4 for any realistic n. That's effectively constant.

โš ๏ธ Edge cases

Nodes are 1-indexed, so size the arrays n + 1. The input is guaranteed to be a tree plus exactly one extra edge, so the first edge that joins two nodes already in the same group is the one that appears last among the cycle's edges, which is exactly what's asked. The same pattern solves "Number of Provinces" and "Graph Valid Tree".