= Disjoint-set union operation
{title2=$\operatorname{unite}(x,y)$}
The <disjoint-set union operation> first uses the <disjoint-set find operation> to locate the <blocks of a set partition> containing $x,y$. If they are different <blocks of a set partition> $A,B$, replace them by their <union> $A\cup B$; every other <block of a set partition> stays as it was. If the two <disjoint-set representatives> agree, no merge is needed. Here `unite` returns `True` exactly when it merges two different <blocks of a set partition>. A successful call decreases their count by one; a redundant call preserves it. The name `union` is also customary. Some interfaces instead accept already found <disjoint-set representatives>, making that linking step a separate operation.
For an original example, initialize $X=\{1,2,3,4,5,6,7\}$ as seven <singleton sets>. Apply the calls in this order:
$$
\operatorname{unite}(2,1),\ \operatorname{unite}(4,3),\ \operatorname{unite}(2,4),\ \operatorname{unite}(6,5),\ \operatorname{unite}(2,6),\ \operatorname{unite}(1,2).
$$
The first five calls succeed. After the third, the <partition of a set> is $\{\{1,2,3,4\},\{5\},\{6\},\{7\}\}$; after the fifth it is $\{\{1,2,3,4,5,6\},\{7\}\}$. The sixth returns `False`: $1,2$ are already together. The <blocks of a set partition> number $7,6,5,4,3,2,2$, counting the initial state. A <disjoint-set find operation> on $7$ cannot merge it with any other member.
\Image[/disjoint-set-union-seven-element-partitions.png]
{title=Five successful <disjoint-set union operations> and one redundant call on seven elements}
{description=Each coloured enclosure is one <block of a set partition>. Columns identify the same seven members in every row; enclosures show membership rather than parent pointers.}
This is exactly the kind of changing membership needed by <Kruskal component merging>: an accepted <edge> joins two current <connected components of a graph>, while an <edge> whose endpoints already have equal <disjoint-set representatives> is rejected. The existing <Kruskal's algorithm worked example> follows that application. A <disjoint-set forest> stores membership efficiently without repeatedly enumerating every <block of a set partition>.
Back to article page
