8.4 Union Find (Disjoint Set)

Demo: Redundant Connection — LC 684 (Medium — Google/Meta High)

Statement (Demo): A tree had one extra edge added, creating a cycle. Given edges, return the edge that can be removed so the graph is a tree again. Example: edges=[[1,2],[1,3],[2,3]] → [2,3] | ⚡ edges.length ≤ 1000

Approach: For each edge, find the roots of both ends — if they share a root, the ends are already connected, so this edge closes a cycle. Otherwise union them. Path compression in find makes it effectively O(1).

function findRedundantConnection(edges) {
  const parent = Array.from({ length: edges.length + 1 }, (_, i) => i);
  const find = (x) => (parent[x] === x ? x : (parent[x] = find(parent[x]))); // path compression
  for (const [a, b] of edges) {
    const ra = find(a),
      rb = find(b);
    if (ra === rb) return [a, b]; // already connected → cycle
    parent[ra] = rb; // union
  }
}

Complexity: Time O(n α(n)) ≈ O(n), Space O(n)