Graphs · LC #684
Redundant Connection
Find the last edge that creates a cycle in an undirected graph-tree using Union-Find - the edge whose two endpoints already share the same root.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
You are given a graph that started as a tree with `n` nodes labeled 1 to n, with one additional edge added. The added edge connects two different vertices and is not a self-loop. Return an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input.
Sample I/O
Input: edges=[[1,2],[1,3],[2,3]] Output: [2,3] Input: edges=[[1,2],[2,3],[3,4],[1,4],[1,5]] Output: [1,4]
Intuition
How to Think About It
Intuition
A tree with n nodes has n-1 edges. When we add edges one by one, the first edge that connects two nodes already in the same component creates a cycle - that's the redundant edge. Union-Find detects this in near-O(1) per edge: if find(u) == find(v) before union, the edge (u, v) is redundant.
Core Concept
Union-Find (DSU) with path compression. Process edges in order. For each edge (u, v): if find(u) == find(v), they're already connected - return this edge as redundant. Otherwise, union the two components (parent[find(u)] = find(v)). Path compression in find() keeps amortized cost near O(1).
When to use
Detecting the first cycle-forming edge in an undirected graph; dynamic connectivity problems; Kruskal's MST; any problem requiring incremental union of sets with membership queries.
When NOT to use
Directed graphs (DFS 3-state coloring is better). When you need the specific cycle path, not just the offending edge. When edges can be removed (DSU is hard to "undo" without rollback).
Key Insights
What to Know Cold
- Path compression in find() - set parent[x] = parent[parent[x]] or fully flatten - keeps tree height near 1.
- Union by rank prevents the DSU tree from degenerating into a linked list.
- Since we return the LAST redundant edge and process in order, the first find(u)==find(v) hit is our answer.
- DSU is the cleanest solution; DFS-based cycle detection also works but is less elegant here.
- For the directed-graph variant (LC #685), need DFS + in-degree analysis instead.
1 example
Worked Examples
Union-Find cycle detection
edges=[[1,2],[1,3],[2,3]] - edge [2,3] forms the cycle.
Process each edge; union components; detect when both endpoints already share root.
function findRedundantConnection(edges: number[][]): number[] {
const n = edges.length;
const parent = Array.from({ length: n + 1 }, (_, i) => i);
const find = (x: number): number => {
while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; }
return x;
};
for (const [u, v] of edges) {
const pu = find(u), pv = find(v);
if (pu === pv) return [u, v]; // cycle detected
parent[pu] = pv;
}
return [];
}Output: [2, 3]
Classic Union-Find application. Interviewers check whether you know DSU and can implement path compression, and whether you articulate why DSU is better than DFS here.