Redundant Connection — Step-by-Step Visualization

Algorithm Pattern

Union Find (Disjoint Set)

Key Idea

A tree with $n$ nodes must have $n-1$ edges. The 'redundant' edge is the one that connects two nodes that are already in the same connected component. We can use Union Find to keep track of disjoint sets. For each edge $(u, v)$, if `find(u) == find(v)`, then $u$ and $v$ are already connected, so $(u, v)$ is the redundant edge.

Step-by-Step Approach

1. Initialize Union Find with $n$ sets (each node is its own parent).
2. Iterate through each edge `(u, v)`.
3. If `union(u, v)` returns `False`, it means $u$ and $v$ were already connected.
4. Return the current edge `(u, v)`.

Common Gotchas

• Nodes are labeled 1 to $n$.
• The input is guaranteed to have exactly one redundant edge.
• Union Find with path compression and union-by-rank/size is $O(n\alpha(n))$.