---
title: "Union-Find"
description: "Disjoint sets with path compression"
source: https://vizlearn.app/algorithms/data-structures/union-find
access: premium (interactive player requires Lifetime; this doc is free)
---

# Union-Find (Disjoint Set Union)

Union-Find answers one question fast, over and over, as a graph keeps changing: *are these two things already connected?* It maintains a collection of disjoint sets and supports two operations — `union(a, b)` merges the sets containing `a` and `b`, and `find(x)` returns a representative for `x`'s set. With two small optimizations, both run in effectively constant time.

Two elements are in the same set exactly when their finds match.

That one question — *already connected?* — is the engine behind Kruskal's minimum spanning tree (add an edge only if its endpoints are in different sets), cycle detection in an undirected graph, counting connected components, and percolation or network-connectivity checks. Whenever you union things together and keep asking what's reachable from what, this is the structure.

The forest is one integer array. `parent[i]` holds the parent of element `i`; a node that is its own parent (`parent[i] == i`) is a root, the representative of its set. Sets are trees, the forest is the data structure, and `find` is just "follow parent pointers up until you reach a root." That is the entire idea — everything else is making those trees stay short.

## How It Works: Rank and Compression Keep the Trees Short

`find(x)` walks up: read `parent[x]`, move to it, repeat until you hit a node that points to itself. That root names the set.

`union(a, b)` calls `find` on both. If the roots are equal, the elements are already in one set and there is nothing to do. Otherwise you point one root at the other — and *which* one you choose is where performance is won or lost.

The naive choice is to always link the same way (`parent[find(a)] = find(b)`). Run `union(0,1)`, `union(1,2)`, `union(2,3)`… and you build a single leaning chain: every union adds a level, and a later `find` has to walk the whole height. That is O(n) per operation — Union-Find with the cleverness removed.

Two fixes turn that chain into a flat bush:

- **Union by rank.** Each root carries a `rank`, an upper bound on its tree's height. When you merge, link the root with the *lower* rank under the one with the higher rank, so the merged rank — the height bound — stays the larger input's. Only when ranks tie does the bound grow — and then the winner's rank goes up by one. A root of rank `r` needs at least 2ʳ elements, so height stays logarithmic on its own.
- **Path compression.** Every `find` already visits each node on the path to the root. Before returning, point all of them straight at the root. The walk paid for the climb; compression banks it, so the next `find` on any of those nodes is a single hop — until a later union links that root under another.

Apply both and the amortized cost per operation is O(α(n)), where α is the inverse Ackermann function — below 5 for any input that fits in the observable universe. Effectively constant, provably not quite.

## Union-Find Step by Step

The player opens on the **Optimized** variant with six elements, `0` through `5`, each its own singleton set — six separate boxes above a `parent[]` array where every cell points at itself. Play the seeded demo: `union(0,1)`, `union(2,3)`, `union(4,5)`, `union(0,2)`, `union(0,4)`, then `find(5)` twice.

The first three unions each merge two singletons. `union(0,1)` finds roots `0` and `1`, both rank 0; ties go to the first, so `1` links under `0` and `0`'s rank becomes 1 — watch `parent[1]` flip from `1` to `0` in the array as the node slides beneath `0`. `union(2,3)` and `union(4,5)` do the same, leaving three little two-node trees rooted at `0`, `2`, and `4`, each rank 1.

`union(0,2)` is the first merge of two non-singleton trees. Both roots have rank 1, so it is another tie: `2` links under `0`, and `0`'s rank climbs to 2. Now `0` owns `1` directly and `2` (which still carries `3`), so node `3` sits at depth 2. `union(0,4)` is different — `0` has rank 2, `4` has rank 1. The lower rank loses: `4` links under `0` with **no** rank bump, because attaching a rank-1 tree under a rank-2 root cannot raise the bound. Everything is now one set rooted at `0`, and the deepest nodes (`3` and `5`) sit two levels down.

`find(5)` is the payoff. The cursor reads `parent[5] = 4` and climbs to `4`, reads `parent[4] = 0` and climbs to `0`, which points at itself — root found. Then path compression fires: `5` is re-pointed straight to `0`, its edge swinging up and `parent[5]` rewriting from `4` to `0` in the same beat. Node `5` was at depth 2; now it is a direct child of the root. The demo then runs `find(5)` a second time, and this time the cursor takes a single hop — `parent[5]` is already `0`, nothing left to compress. That is the discount made concrete: the first find pays once to flatten the path, and every find after it collects the savings. Multiplied across a run of operations, that is why Union-Find is fast.

Flip the variant to **Naive** to see the contrast on its own telling input: chained unions (`union(0,1)`, `union(1,2)`, …) build a tall leaning chain, and the demo's `find(0)` has to walk the entire height with nothing compressed away. Same style of unions, opposite tree shape — that is the whole argument for the two optimizations, and it plays from the first beat so you watch the chain grow link by link.

## Time and Space Complexity

| Operation | Optimized (rank + compression) | Naive |
|---|---|---|
| `find` | O(α(n)) amortized | O(n) worst case |
| `union` | O(α(n)) amortized | O(n) worst case |
| Space | O(n) | O(n) |

The space is one array (two, counting `rank`) — there are no per-node objects or child pointers, only `parent[i]`. The time bound needs both optimizations: rank alone gives O(log n); compression alone shortens visited paths but does not justify the same combined bound; together they reach the inverse-Ackermann bound. This lesson links the lower-rank root by **rank**; **union by size** (track each tree's element count, link the smaller under the larger) is an equally standard choice with the same asymptotics — pick one and keep it.

## Edge Cases

- **`union` of two already-connected elements** — both finds return the same root, so the operation does nothing. The optimized code returns early; the naive code runs a harmless self-assignment.
- **`find` on a root** — the node points at itself, so the walk ends immediately with zero hops and nothing to compress.
- **`find` on a direct child of a root** — one hop to the root, and compression has nothing to flatten (the node already points at the root).
- **`union(a, a)`** — `a` is already in its own set with itself, so this is the already-connected case.
- **An untouched singleton** — elements you never union stay as their own set; the set count only drops when two *different* sets merge.

## Common Mistakes

- **Skipping `find` and comparing `parent[a]` to `parent[b]`.** Two elements can share a set without sharing a parent — they share a *root*. Connectivity is a `find`-to-`find` comparison, never a parent-to-parent one.
- **Linking the higher-rank root under the lower-rank one.** That is union by rank backwards: it raises the height bound and throws away the whole point. Always link lower rank under higher rank.
- **Bumping the rank on every union.** Rank only increases when two equal-rank roots merge. Incrementing it every time inflates the bound and defeats the balancing logic.
- **Expecting `rank` to equal the exact tree height after compression.** Compression can shorten a tree without lowering its root's rank, so rank becomes an upper bound, not the true height. That is fine — it is still a valid merge key, and recomputing exact heights would cost more than it saves.
- **Reaching for Union-Find to delete edges or split sets.** It only merges. Sets grow and never break apart; a problem that removes connections needs a different structure (or the whole thing rebuilt offline in reverse).