Redundant Connection
Last Updated: April 5, 2026
Understanding the Problem
We're given what was originally a tree with n nodes, but someone snuck in one extra edge. That extra edge creates exactly one cycle in the graph. Our job is to find which edge we can remove to break the cycle and restore the tree structure. If multiple edges could work, we pick the one that appears last in the input array.
Here's the key insight: a tree with n nodes has exactly n - 1 edges. We're given n edges (since n == edges.length), which means exactly one edge is redundant. That redundant edge is the one that, when added, connects two nodes that were already connected through some path. In other words, it's the edge that completes a cycle.
So the question boils down to: as we process edges one by one, which edge connects two nodes that are already in the same connected component?
Key Constraints:
3 <= n <= 1000→ With n up to 1000, even O(n^2) would run comfortably. But O(n) or O(n * alpha(n)) is straightforward with Union Find.n == edges.length→ There are exactly n edges in a graph with n nodes. Since a tree has n-1 edges, exactly one edge is redundant.1 <= a_i < b_i <= n→ Nodes are 1-indexed, and edges are given with the smaller node first. No self-loops.
Approach 1: DFS Cycle Detection
Intuition
The most intuitive approach: process edges one at a time, building a graph as we go. Before adding each edge, check whether the two endpoints are already connected using DFS. If they are already connected, adding this edge would create a cycle, so this is our redundant edge.
Since we process edges in order and the problem guarantees exactly one cycle, the last edge that connects two already-connected nodes is our answer.
Algorithm
- Create an adjacency list for the graph (initially empty).
- Iterate through each edge
[u, v]in order. - Before adding the edge, run DFS from
uto see if we can reachvusing the edges already in the graph. - If
vis reachable fromu, this edge creates a cycle. Return it. - Otherwise, add the edge to the adjacency list and continue.
Example Walkthrough
Code
- Time Complexity: O(n^2). For each of the n edges, we run a DFS that visits up to n nodes.
- Space Complexity: O(n). The adjacency list, visited array, and DFS stack each use O(n) space.
This approach works but runs DFS for every edge. What if we tracked connectivity incrementally so checking it was nearly instant?
Approach 2: Union Find (Optimal)
Intuition
Union Find (also called Disjoint Set Union) is the perfect tool here. It maintains a collection of disjoint sets and supports two operations: find (which set does an element belong to?) and union (merge two sets). Both operations run in nearly O(1) with path compression and union by rank.
The idea is clean: process each edge in order. For each edge [u, v], check if u and v are already in the same set. If they are, this edge is the redundant one. If they're not, merge their sets using union.
Union Find tracks connected components incrementally. Each union operation merges two components, and each find operation determines which component a node belongs to. Path compression makes find nearly O(1) by flattening the tree structure: every node points directly to its root after the first lookup. Union by rank keeps the trees balanced by always attaching the shorter tree under the taller one.
Algorithm
- Initialize a Union Find structure with n+1 elements (nodes are 1-indexed).
- For each edge
[u, v]in the input array:
a. Call find(u) and find(v) to get their root representatives.
b. If the roots are the same, u and v are already connected. Return this edge.
c. Otherwise, call union(u, v) to merge their components.
- Return an empty array (should never reach here given problem constraints).
Example Walkthrough
Code
- Time Complexity: O(n * alpha(n)), effectively O(n). We process n edges, each requiring two find and at most one union operation, all nearly O(1) with path compression and union by rank.
- Space Complexity: O(n). The parent and rank arrays each use O(n) space.