Union-Find (Disjoint Set)

Find/Union O(α(n))Space O(n)

Tracks a partition of elements into disjoint sets. Union merges two sets by rank and Find locates a set's root with path compression, giving near-constant amortized time.

0root

1root

2root

3root

4root

5root

6root

7root

8 separate elements. Union to merge sets; Find to locate a set's root.

On pathRoot / resultEach set is outlined in its own colour.

About Union-Find (Disjoint Set)

Tracks a partition of elements into disjoint sets. Union merges two sets by rank and Find locates a set's root with path compression, giving near-constant amortized time.

Time complexity: O(α(n)). Space complexity: O(n).

Use the interactive visualizer above to run Union-Find (Disjoint Set) on your own input and watch every comparison, swap, and operation animate step by step — pause, scrub, or replay at any speed.

All data structures

Union-Find (Disjoint Set)

Find/Union O(α(n))Space O(n)

Tracks a partition of elements into disjoint sets. Union merges two sets by rank and Find locates a set's root with path compression, giving near-constant amortized time.

0root

1root

2root

3root

4root

5root

6root

7root

8 separate elements. Union to merge sets; Find to locate a set's root.

On pathRoot / resultEach set is outlined in its own colour.

About Union-Find (Disjoint Set)

Tracks a partition of elements into disjoint sets. Union merges two sets by rank and Find locates a set's root with path compression, giving near-constant amortized time.

Time complexity: O(α(n)). Space complexity: O(n).

Use the interactive visualizer above to run Union-Find (Disjoint Set) on your own input and watch every comparison, swap, and operation animate step by step — pause, scrub, or replay at any speed.