Introduction
Disjoint Set Union (DSU) is a data structure for maintaining a collection of disjoint sets.
Initially, each element belongs to its own set. Then DSU supports operations that allow us to merge sets and determine which set a given element belongs to.
In the classical version, DSU supports three operations:
make_set(x)— create a new set containing only elementx;find_set(x)— find the representative (leader) of the set containingx;union_sets(x, y)— merge the sets containingxandy.
Implementation
Each set is represented as a rooted tree.
- the vertices of the tree are the elements of the set;
- the root of the tree is called the leader (or representative) of the set.
So DSU stores a forest of trees, where each tree corresponds to one set.
Two elements belong to the same set if and only if their leaders are the same.

Naive Solution
To implement this idea, we use an array parent, where parent[x] stores the parent of vertex x.
If x is the root of its tree, then parent[x] = x.
Operations
-
make_set(x)
Create a new set containing onlyx. -
find_set(x)
Find the root of the tree containingx. -
union_sets(x, y)
First find the leaders ofxandy. If they are different, attach one tree to the other.
In the worst case, both find_set and union_sets may take time.
Faster Solution: Union by Size
The main problem with the naive version is that the trees can become very deep.
To improve this, when merging two sets, we always attach the tree to the one.