 Solution

The blocks of a set partition are the nonempty fibres of rep, and their shared values are their disjoint-set representatives. Initially $re p = \emptyset$ , so

S = \emptyset

. 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

re p^{'} (x) = x

. For union(x,y), snapshot

r_{x} = re p_{0} (x)

and

r_{y} = re p_{0} (y)

, keep

S

unchanged, and set

re p^{'} (z) = {r_{x} re p_{0} (z) re p_{0} (z) = r_{y}, otherwise .

(2)

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.

 Read the full article

 New to topics? Read the docs here!