Union-Find Data Structure

data-structures

Definition

Union-Find Data Structure

The union-find data structure is a data structure that stores a collection of disjoint sets ($\forall i,j:S_i\cap S_j=\varnothing$) and provides the following three major functions:

1. $\mathrm{makeset}(v)$: Creates a new disjoint set $S_v=\{v\}$ where $v$ is called representative of $S_v$.
2. $\mathrm{union}(v,w)$: Merges two disjoint sets, $S_v$ and $S_w$, where $v$ and $w$ are the representatives of their respective sets.
3. $\mathrm{findset}(v)$: Finds the set to which $v$ belongs.

Implementation

The main idea of the implementation is to represent the disjoint sets as strongly connected graph components:

The above shows two disjoint sets $S_i$ and $S_h$. We notice that

• $\mathrm{findset}(c)=\mathrm{findset}(i)=S_i=\{i,c\}$
• $\mathrm{findset}(g)=\mathrm{findset}(f)=\mathrm{findset}(h)=S_h=\{h,f,g\}$

Trivially, creating a new disjoint set using $\mathrm{makeset}(z)$ would result in a subgraph with a single node $z$.

To union those two sets, we just have to change the parent of $i$ to $h$ (without loss of generality):

Merging two disjoint sets using $\mathrm{union}(v,w)$ have a time complexity of $O(1)$ since we just need to update $parent[i]=h$, with $parent$ being an array.

Creating a set using $\mathrm{makeset}(v)$ also has a time complexity of $O(1)$.

However, contra-intuitively, $findset(v)$ has an amortised time complexity of $O(1)$ since when iterating over the chain, we can just change the parent of each node in the disjoint set to the representative of that disjoint set, and always attach the lower-depth subgraph to the greater-depth subgraph. Thus:

$$\begin{array}{rl}parent[c]& =parent[i]\\ =parent[f]& =parent[g]\\ =parent[h]& =h\end{array}$$

where each array access has a time complexity of $O(1)$. Therefore, the amortised time complexity of $\mathrm{findset}(v)$ is $O(1)$.