= Solution
A sufficient <representation invariant> is:
* Both <arrays> have length `capacity`, with $capacity>0$ and $0\leq used\leq capacity$.
* The active keys `elements(0 until used)` are pairwise distinct.
* For each active index $k$, `representatives(k)` equals some active key `elements(j)`.
* Every such representative is fixed: if `representatives(k) == elements(j)`, then `representatives(j) == elements(j)`.
The <abstraction function> is
$$
rep=\{\,elements(k)\mapsto representatives(k)\mid0\leq k<used\,\}.
$$
The last two conditions ensure each representative is a genuine member of its own block and that the abstract <function> is <idempotent function>. Cells beyond `used` are unconstrained and ignored. When `used == 0`, these conditions hold vacuously and the <abstraction function> yields the empty map. This is an explicit-key version of <quick-find>, rather than a parent-pointer <disjoint-set forest>.
Back to article page
