LeetCode 684 · Medium · Graphs

Redundant Connection

A tree with nodes 1 to n got one extra edge, so the n edges now contain exactly one cycle. Return the edge you can remove to get a tree back; if several work, return the one that appears last in the input.

O(n·α(n))time
O(n)space
union-findby rank, path halving

3–10 pairs [u, v] with nodes 1 to n (n = number of edges) · a connected tree plus one extra edge

par par[i] = parent of i · a root points to itself (green) · index 0 unused

rank size of the tree under each root

public int[] findRedundantConnection(int[][] edges) { int[] par = new int[edges.length + 1]; int[] rank = new int[edges.length + 1]; for (int i = 0; i < par.length; i++) { par[i] = i; rank[i] = 1; } for (int[] e : edges) { if (!union(par, rank, e[0], e[1])) { return e; } } return new int[0];}private int find(int[] par, int n) { int p = par[n]; while (p != par[p]) { par[p] = par[par[p]]; // path halving p = par[p]; } return p;}private boolean union(int[] par, int[] rank, int n1, int n2) { int p1 = find(par, n1); int p2 = find(par, n2); if (p1 == p2) { return false; // already connected } if (rank[p1] > rank[p2]) { par[p2] = p1; rank[p1] += rank[p2]; } else { par[p1] = p2; rank[p2] += rank[p1]; } return true;}
[n1, n2]
—
p1
—
p2
—
rank[p1], rank[p2]
—
sets
—

Why it works

  1. Brute force removes each edge in turn, from the last, and checks with a DFS whether the rest is still connected: O(n²).
  2. Invariant: two nodes share a root exactly when the edges seen so far connect them. An edge whose ends already share a root closes a cycle. Edges are read in input order, so the first such edge is the last edge of the cycle in the input: the one to return.
  3. Near O(1) per edge: union by rank hangs the smaller tree under the larger root, so trees stay shallow, and path halving (par[p] = par[par[p]]) shortens every path find walks. Together that is O(α(n)) amortised, at most 4 or 5 in practice.
  4. Pitfall: link the roots, never the nodes themselves: par[p2] = p1, not par[n2] = n1, or a whole subtree gets cut loose. (NeetCode's rank is really a size, which works just as well.)
  5. Related: Number of Connected Components (323) counts successful unions with the same structure; Redundant Connection II (685) is the directed version.