= Solution
Choose a fixed positive capacity $C$ and represent the abstract state by a finite <partial function> $rep:\mathbb Z\rightharpoonup\mathbb Z$. Its <domain of a partial function> $S$ has at most $C$ members; each $rep(x)$ belongs to $S$ and is a fixed point:
$$
rep(rep(x))=rep(x)\qquad(x\in S).
$$
The <blocks of a set partition> are the nonempty fibres of `rep`, and their shared values are their <disjoint-set representatives>. Initially \b[$rep=\varnothing$], so $S=\varnothing$. Representatives need not be the minimum members of their blocks.
``
trait DisjointSets {
val capacity: Int
// State: rep is a finite idempotent map, |dom rep| <= capacity.
// Initially: rep is empty; capacity is fixed and positive.
// Pre: x is absent and |dom rep| < capacity.
// Post: add x -> x; leave every old mapping unchanged.
def makeSet(x: Int): Unit
// Pre: x belongs to dom rep.
// Post: state unchanged; return rep(x).
def find(x: Int): Int
// Pre: x and y belong to dom rep.
// Post: merge their blocks, retaining old rep(x).
def union(x: Int, y: Int): Unit
}
``
Precisely, `makeSet(x)` extends the <domain of a partial function> by $x$ with $rep'(x)=x$. For `union(x,y)`, snapshot $r_x=rep_0(x)$ and $r_y=rep_0(y)$, keep $S$ unchanged, and set
$$
rep'(z)=\begin{cases}r_x&rep_0(z)=r_y,\\rep_0(z)&\text{otherwise}.\end{cases}
$$
This merges the two blocks and keeps the representative of the first argument's block. If $r_x=r_y$, it is an identity operation. This deterministic design choice satisfies <disjoint set union> without imposing minimum-element representatives. The capacity bound is explicit in the <abstract data type> so that the bounded implementation does not silently strengthen `makeSet`'s <precondition>.
Back to article page
