Disjoint Set Union (DSU)

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 element x;
• find_set(x) — find the representative (leader) of the set containing x;
• union_sets(x, y) — merge the sets containing x and y.

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 only x.

• find_set(x)
  Find the root of the tree containing x.

• union_sets(x, y)
  First find the leaders of x and y. If they are different, attach one tree to the other.

In the worst case, both find_set and union_sets may take $O(n)$ 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.