System of disjoint sets

System of disjoint sets

Introduction

DSU (Disjoint Set Union) provides the following capabilities: we are given several elements, each of which initially is a separate set. DSU supports the operation of merging any two sets and allows determining which set a particular element belongs to. In the classic version, a third operation is also introduced — creating a set from a new element.

Thus, the DSU interface consists of three functions:

• make_set(x) — creates a new set from a single element $x$.
• find_set(x) — finds the set in which element $x$ is located (usually returns the leader of the set).
• union_sets(x, y) — merges the sets containing elements $x$ and $y$.

Implementation

We will represent each set as a rooted tree. The vertices are the elements of the set. The root of the tree is called the leader of the set. Then we get a forest of trees, where each tree corresponds to one set.

Two vertices are in the same set if and only if the leaders of their trees coincide.

Naive solution

Let’s create an array parent, where parent[x] is the parent of vertex (and for the root).