Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Concept

Union-Find (DSU)

Disjoint sets · find + union

Disjoint Set Union

time ~O(α(n)) per opspace O(n)

step 1 / 8

disjoint sets

parent[]

0	1	2	3	4
0	1	2	3	4

Disjoint Set Union


▸
1parent[i] ← i           // each node its own set
2find(x): while parent[x] != x: x = parent[x]; return x
3union(a, b):
4    ra, rb ← find(a), find(b)
5    if ra != rb: parent[rb] = ra
6// same set? ⇔ find(a) == find(b);  #sets = distinct roots

state

sets5
parent[0,1,2,3,4]

line 1Union-Find tracks a collection of DISJOINT sets under two questions: "are a and b in the same set?" and "merge a's set with b's set". Start with every element in its OWN set: parent[i] = i, so each node is its own root.