Union find
==========

The `union-find`_, or disjoint-set, data structure is used to model a
collection of non-overlapping sets of elements. The three supported
operations are as follows.

1. ``make_set(x)``

   Adds a single element ``x`` that is a member of a new singleton set
   containing ``x``.

2. ``find(x)``

   Finds the set that ``x`` is a part of. This function returns a
   representative element of that set.

3. ``union(x, y)``

   Merges the sets containing ``x`` and ``y`` into a single set.

Note that with our definition of ``find`` we can determine if ``x``
and ``y`` belong to the same set by comparing their representative
elements, i.e. ``find(x) == find(y)``.

The union find data structure can be used to model the connected
components of a graph. This is useful, for example, when implementing
Kruskal's algorithm for computing minimum spanning trees.

.. _union-find: https://en.wikipedia.org/wiki/Disjoint-set_data_structure


Linked list implementation
--------------------------

A straightforward implementation of the union-find data structure
represents each set with a linked list of elements. The representative
of a set is the head of the list. We could implement the operations as
follows. Here we assume all elements are pointers to a node that have
a ``parent``, ``child``, and ``head`` pointers pointing to the
previous, next, and first elements of the list, if any.

.. code-block:: none

   MAKESET(x)
     create a new linked list containing x

   FIND(x)
     if x has a head
       return x.head
     else
       return x

   UNION(x, y)
     while x has child
       x = x.child

     rootY = FIND(Y)
     rootY.parent = x
     rootY.head = x.head

     while rootY has child
       rootY.child.head = x.head
       rootY = rootY.child

Here we use the head element of a list as its representative, and we
append linked lists together to merge them.

Note that this implementation has the following runtime
characteristics, where throughout :math:`n` is the total number of
elements being tracked.

1. ``make_set(x)`` is :math:`O(1)` time

2. ``find(x)`` is :math:`O(1)` time

3. ``union(x, y)`` is :math:`O(n)` time

If we always append the smaller list to the larger list, then
performing :math:`m` ``MAKESET``, ``FIND``, or ``UNION`` operations on
:math:`n` elements takes :math:`O(m + n \log n)` time. This helps
because we only need to update the ``head`` pointer on the smaller of
the lists, and so we always have to update at most half of a set.


Disjoint forests structure
--------------------------

We can improve the runtime by using a more interesting data structure,
along with some optimizations. We now represent each set as a rooted
tree. The representative of a set is the root of the tree. ``MAKESET``
is implemented by creating a tree with a single root node. ``FIND``
returns the root of the tree, found by traversing the tree upwards
until a node is found with no parent. ``UNION`` is implemented by
attaching the root of one tree as the child of the root of another.


Union by rank
~~~~~~~~~~~~~

The first optimization is similar to the one we employed with linked
lists, i.e. always appending to the larger list. Here we always merge
the smaller tree into the larger tree. Note that this increases the
depth of the tree being merged into only if the height of the two
trees were equal beforehand. Both ``UNION`` and ``FIND`` can be
implemented in :math:`O(\log n)` time with this optimization.


Path compression
~~~~~~~~~~~~~~~~

In path compression, whenever we traverse the tree for a ``FIND``
operation we attach all nodes traversed in getting to the root
directly to the root; this maintains the validity of the structure,
since the root is the representative for all these nodes. The
intuition is that any subsequent calls to ``FIND`` on the same node or
any recursive parent of the node will be faster.

With both union-by-rank and path compression, the amortized time per
``FIND`` or ``UNION`` operation is :math:`O(\alpha(n))`, where
:math:`\alpha(n)` is defined as the inverse of :math:`A(n, n)`, where

.. math::

   A(m, n) = \begin{cases}
     n + 1, & m = 0 \\
     A(m - 1, 1), & n = 0 \\
     A(m - 1, A(m, n - 1)), & \text{otherwise}
   \end{cases}

is the Ackermann function. It can be safely assumed that
:math:`\alpha(n) \le 5` for any real-world inputs, since the Ackermann
function is increasing in each of its arguments and :math:`A(4, 4) =
2^{2^{2^{65536}}} - 3`.