🕸️ Union-Find (Disjoint Sets)

💡 Click one node then another to union them. Roots have a double ring; colour = set.

Find cost (n = 12)

sets = 12 · tallest tree height = 0

naive union	up to n = 12
+ union by rank	≤ log₂ n = 4
+ path compression	≈ α(n) ≤ 4

Both optimizations → amortised near-constant per operation.

Find / Union

1root: parent[x] == x
2find(x): while parent[x] ≠ x: x = parent[x]
3  (compress: parent[x] = root)
4union(a, b):
5  ra, rb = find(a), find(b)
6  if ra == rb: return  // already joined
7  attach smaller-rank root under larger

Speed: 55%

Union-Find Visualizer: Disjoint Sets, Union by Rank & Path Compression

This union-find (disjoint set) simulator shows a forest where each tree is one set: every node points to a parent, and find() walks up to the root that names the set. Union joins two roots; toggle union-by-rank to always hang the shorter tree under the taller, and path compression to re-point every node on a find path straight at the root — flattening the tree before your eyes. A find-cost card contrasts the three regimes: naive union can degrade to O(n), union-by-rank caps height at log n, and both together give amortised O(α(n)) where the inverse Ackermann function is at most 4 for any real input. The signature interaction is hands-on: click one node then another to union them, and switch on Predict mode to guess whether two elements are connected before find() reveals the answer.

What you can do in this simulation

Click one node then another to union their sets — roots carry a double ring and each set gets its own colour
Toggle Union by rank and Path compression independently and watch trees stay flat or grow into a chain
Run connectivity queries: find() lights up the path to each root and reports CONNECTED or NOT
Predict mode: guess connected / not connected before the query resolves, with a running score
A find-cost card compares naive O(n) vs union-by-rank O(log n) vs both ≈ α(n) ≤ 4, with live set count and tallest-tree height

Concepts covered

union-find · disjoint set union · union by rank · path compression · inverse Ackermann · connected components · amortised analysis

Related simulations

Browse all Technology simulations →

Free to use in your browser — no signup required. Found a bug or have an idea to make it better? Tell us.

Please wait

Loading technology simulations

The requested content is still loading.

Finished experimenting?

Save one completion to this browser's signed guest ledger, or directly to your account when signed in.

1root: parent[x] == x

2find(x): while parent[x] ≠ x: x = parent[x]

3 (compress: parent[x] = root)

4union(a, b):

5 ra, rb = find(a), find(b)

6 if ra == rb: return // already joined

7 attach smaller-rank root under larger

Union-Find Visualizer: Disjoint Sets, Union by Rank & Path Compression

What you can do in this simulation

Click one node then another to union their sets — roots carry a double ring and each set gets its own colour

Toggle Union by rank and Path compression independently and watch trees stay flat or grow into a chain

Run connectivity queries: find() lights up the path to each root and reports CONNECTED or NOT

Predict mode: guess connected / not connected before the query resolves, with a running score

A find-cost card compares naive O(n) vs union-by-rank O(log n) vs both ≈ α(n) ≤ 4, with live set count and tallest-tree height