Union-Find | AlgoViz

Union-FindO(alpha(n))

Best on a larger screen

AlgoViz's interactive walkthrough is built for a tablet or larger. Rotate your device or open it on a wider screen to explore the visualization.

Loading walkthrough.

SPEED

WalkthroughSTEP 0 / 0

Loading walkthrough.

Keyboard shortcuts

1function find(x):

2 root = x

3 while parent[root] != root:

4 root = parent[root]

5 while parent[x] != root: # path compression

6 parent[x] = root; x = next

7 return root

8function union(a, b):

9 ra = find(a); rb = find(b)

10 if ra == rb: return # already connected

11 if size[ra] < size[rb]: swap(ra, rb)

12 parent[rb] = ra # attach smaller under larger

13 size[ra] += size[rb]

Edit the input and run it through the same engine that drives the walkthrough.

elements: A B C D E F
union A B
union C D
union E F
union A C
union A E
find D
union D F

Ask about this step or this algorithm.

Try: "Why a heap here?" or "What does this counter track?"