Disjoint Sets (Union-Find)

Some problems keep a collection of items partitioned into disjoint groups that only ever merge, never split, and repeatedly ask whether two items currently share a group. Are these two cities on the same electrical grid? Do these two pixels belong to the same connected region? Does adding this edge to a graph create a cycle? The disjoint-set (or union-find) data structure answers exactly these questions, and does so in near-constant amortized time per operation¹, slow-growing enough that for any realistic input it is effectively $O(1)$.

There is a recurring lesson in the design of efficient algorithms: the right data structure is what makes an algorithm fast. Dijkstra's and Prim's shortest- path and MST algorithms are correct with any priority queue, but their speed hinges on the queue: a binary heap gives $O(m\log n)$, while a Fibonacci heap (with amortized $O(1)$ $\text{Decrease-Key}$) shaves it toward $O(m+n\log n)$. Kruskal's MST illustrates the same point with a different structure. The algorithm is one line of logic, and every bit of its efficiency comes from the disjoint-set structure beneath it. We will build that structure from the ground up and improve it from $\Theta (n)$ per query down to inverse Ackermann.

The disjoint-set ADT

We maintain a collection $\left\{S_1,S_2,\dots ,S_k\right\}$ of disjoint sets that together partition a universe of elements. Each set is named by a representative, some fixed member of the set chosen by the structure. The ADT has three operations:

• $\text{Make-Set}(x)$ creates a new set whose only member is $x$ (so $x$ is its own representative). $x$ must not already be in any set.
• $\text{Find-Set}(x)$ returns the representative of the set containing $x$. Two elements are in the same set iff they return the same representative.
• $\text{Union}(x,y)$ merges the sets containing $x$ and $y$ into one, picking a representative for the combined set. The two old sets are destroyed.

The query are $x$ and $y$ together? is just the test $\text{Find-Set}(x)=\text{Find-Set}(y)$. After $n$ $\text{Make-Set}$ operations there can be at most $n-1$ Union operations, since each union reduces the number of sets by one.

The forest representation

The fast implementation represents each set as a rooted tree, and the whole collection as a forest.² Every element points only to its parent; the root of each tree is the set's representative and points to itself. There are no child pointers and no key ordering. This is not a search tree, just a tangle of upward pointers whose only job is to lead to a root.

Two sets: $\left\{a,b,c,h\right\}$ with representative $c$, and $\left\{d,e,f\right\}$ with representative $f$. Each node's single arrow points at its parent; the roots loop to themselves. $\text{Find-Set}$ follows parent pointers up to the root; Union makes one tree's root a child of the other's.

So far this is correct but not fast: a careless sequence of unions can build a tall, skinny tree, a path of $n$ nodes, making $\text{Find-Set}$ cost $\Theta (n)$. Two heuristics, used together, flatten the forest and make the structure fast.

from collections.abc import Hashable, Iterable
from typing import Generic, TypeVar, cast

Element = TypeVar("Element", bound=Hashable)

class ForestNode(Generic[Element]):
  """
    One element's node: its value and its parent link.\n
    A node is its own parent exactly when it is the root of its set.\n
  """

  def __init__(self, value: Element) -> None:
    self.value: Element = value
    self.parent: ForestNode[Element] = self

  def __repr__(self) -> str:
    return f"ForestNode({self.value!r})"

class NaiveDisjointForest(Generic[Element]):
  """
    A partition into disjoint sets, stored as a forest of parent pointers\n
    with neither union by rank nor path compression.\n
  """

  def __init__(self, elements: int | Iterable[Element] = 0) -> None:
    """
      Seed the forest. An int `n` makes singletons `0..n-1`; an iterable\n
      makes one singleton node per member.\n
    """
    # an int n means singletons 0..n-1; otherwise seed from the iterable.
    members: Iterable[Element] = (
      cast("Iterable[Element]", range(elements))
      if isinstance(elements, int)
      else elements
    )

    # one singleton node per member.
    self._nodes: dict[Element, ForestNode[Element]] = {}
    for value in members:
      self.make_set(value)

  def make_set(self, value: Element) -> None:
    """
      Create a new singleton set whose only member is `value`.\n
      Does nothing if `value` already belongs to a set.\n
    """
    if value not in self._nodes:
      self._nodes[value] = ForestNode(value)

  def _find_root(self, value: Element) -> ForestNode[Element]:
    """
      The root node of `value`'s set, walking parent links upward.\n
      No path compression: the tree is left exactly as it was.\n
    """
    # follow parent links until a node is its own parent.
    node = self._nodes[value]
    while node.parent is not node:
      node = node.parent
    return node

  def find(self, value: Element) -> Element:
    """
      The representative value of `value`'s set.\n
    """
    return self._find_root(value).value

  def height(self, value: Element) -> int:
    """
      Number of parent hops from `value`'s node up to its root.\n
      A root reports 0. Useful for showing how tall a careless union\n
      order lets the forest grow.\n
    """
    # count parent hops climbing to the root.
    node = self._nodes[value]
    hops: int = 0
    while node.parent is not node:
      node = node.parent
      hops += 1
    return hops

  def union(self, first: Element, second: Element) -> bool:
    """
      Merge the sets of `first` and `second` by hanging the second set's\n
      root beneath the first set's root. Returns False if they already\n
      shared a set.\n
    """
    # already one set: nothing to merge.
    first_root = self._find_root(first)
    second_root = self._find_root(second)
    if first_root is second_root:
      return False

    # hang the second root beneath the first (no rank to guide the choice).
    second_root.parent = first_root
    return True

  def connected(self, first: Element, second: Element) -> bool:
    """
      Whether `first` and `second` belong to the same set.\n
    """
    return self._find_root(first) is self._find_root(second)

A warm-up: labels, and always relabel the smaller side

Before the forest, consider the most naive possible implementation, along with the one idea that already makes it efficient. Keep an array $comp[]$ that stores, for each element, a label naming its current set. Then $\text{Find-Set}(x)$ is just $comp[x]$, a single array lookup, and the same-set test $comp[u]=comp[v]$ is instant. The whole cost is in $\text{Union}$: merging two sets means walking through one of them and rewriting every member's label to match the other.

The question is which set to rewrite. If we are careless and always relabel, say, the set containing $u$, an adversary can force $\Theta (n)$ work on every union. The fix is a single disciplined rule:

To do this efficiently, alongside $comp[]$ keep a list $members[\ell ]$ of the elements currently carrying label $\ell$, plus each set's size; the union then splices the smaller list into the larger and relabels only the short side.

Why does this help so much?

This small example already shows the idea: a structurally trivial rule (relabel the smaller side) plus an amortized doubling argument turns a quadratic-looking cost into $O(n\log n)$. The forest representation below keeps exactly this intuition, the smaller thing yields to the larger, but replaces the explicit relabeling with a single pointer move, so a union becomes $O(1)$ instead of $O(\text{size})$.

from collections.abc import Hashable, Iterable
from typing import Generic, TypeVar, cast

Element = TypeVar("Element", bound=Hashable)

class UnionBySizeLabels(Generic[Element]):
  """
    A partition stored as an explicit label per element, merged by always\n
    relabeling the smaller side.\n
  """

  def __init__(self, elements: int | Iterable[Element] = 0) -> None:
    """
      Seed the structure. An int `n` makes singletons `0..n-1`; an\n
      iterable makes one singleton per member. Each element starts as its\n
      own label, and `members[label]` lists the elements carrying it.\n
    """
    # an int n seeds singletons 0..n-1; an iterable seeds its members.
    seed: Iterable[Element] = (
      cast("Iterable[Element]", range(elements))
      if isinstance(elements, int)
      else elements
    )

    # label maps element -> its set's representative; members is the inverse.
    self._label: dict[Element, Element] = {}
    self._members: dict[Element, list[Element]] = {}
    for value in seed:
      self.make_set(value)

  def make_set(self, value: Element) -> None:
    """
      Create a new singleton set whose only member is `value`, labeled by\n
      itself. Does nothing if `value` is already present.\n
    """
    if value not in self._label:
      self._label[value] = value
      self._members[value] = [value]

  def find(self, value: Element) -> Element:
    """
      The label (representative) of `value`'s set — a single lookup.\n
    """
    return self._label[value]

  def size(self, value: Element) -> int:
    """
      The number of elements in `value`'s set.\n
    """
    return len(self._members[self._label[value]])

  def union(self, first: Element, second: Element) -> bool:
    """
      Merge the sets of `first` and `second`, relabeling the smaller set\n
      to match the larger one. Returns False if they already shared a set.\n
    """
    first_label: Element = self._label[first]
    second_label: Element = self._label[second]
    if first_label == second_label:
      return False

    # keep the larger set's label; relabel the smaller (fewer rewrites).
    larger: Element = first_label
    smaller: Element = second_label
    if len(self._members[larger]) < len(self._members[smaller]):
      larger, smaller = smaller, larger

    # relabel every member of the smaller set to the larger's label.
    for member in self._members[smaller]:
      self._label[member] = larger

    # splice the smaller set into the larger and drop the empty entry.
    self._members[larger].extend(self._members[smaller])
    del self._members[smaller]
    return True

  def connected(self, first: Element, second: Element) -> bool:
    """
      Whether `first` and `second` carry the same label.\n
    """
    return self._label[first] == self._label[second]

  @property
  def count(self) -> int:
    """
      Number of disjoint sets currently held.\n
    """
    return len(self._members)

Everything now hinges on which root we hang beneath the other. Get it wrong and the forest degenerates into exactly the chain from before; get it right and the trees stay flat. The figure contrasts the two outcomes of the same four merges.

Heuristic 1: union by rank

The trouble is unions that make a tall tree a child of a short one, deepening it. Union by rank prevents this. Each root carries a rank, an upper bound on the height of its tree. When uniting two trees, we attach the root of smaller rank beneath the root of larger rank, so the taller tree's height never grows. Only when the two ranks are equal does the height increase, and then by exactly one (and we bump the surviving root's rank).

This single rule already guarantees a logarithmic height bound:

Notice this is the same doubling argument from the warm-up, read from the other direction: there, a set doubled each time an element was relabeled; here, a root's rank rises only when two equal-rank trees merge, which doubles the node count. Either way, ${\log }_{2}n$ is the ceiling, because nothing can double more than that many times.

The figure shows a $\text{Union}$ under this rule. The left tree has rank $2$, the right rank $1$; since their ranks differ, the smaller-rank root $f$ is hung beneath the larger-rank root $c$ and no rank changes. The result still has rank $2$, exactly as the warm-up's smaller side yields to the larger demands, but now it costs a single pointer move rather than relabeling every member.

Heuristic 2: path compression

Path compression attacks the cost from the other side. Each time $\text{Find-Set}(x)$ walks up to the root, it makes a second pass and points every node it visited directly at the root. The path is paid for once; every future $\text{Find-Set}$ on those nodes is then a single hop.

Before, $u$ sits at the bottom of a chain $u\to v\to w\to r$; after $\text{Find-Set}(u)$, the nodes $u$, $v$, $w$ all point straight at $r$. The $\text{Find-Set}$ that pays for the walk leaves the tree much flatter for every later operation.

The recursion bottoms out at the root, and as it unwinds it reassigns every node's parent to that root. With path compression in use, the rank of a root is only an upper bound on its height (compression can make the tree shorter than its rank suggests), which is why the heuristic is called union by rank rather than by height.

The near-constant amortized bound

Used together, union by rank and path compression drive the disjoint-set structure's cost to near-constant.

The function $\alpha (n)$ grows so slowly it is practically constant: $\alpha (n)\le 4$ for every $n$ up to roughly $2^{2^{2^{16}}}$, a number far larger than the count of atoms in the universe. So for any conceivable input, each operation costs amortized $O(1)$.³

The two heuristics achieve this by attacking complementary failure modes: union by rank keeps trees from getting tall in the first place (height $\le \log n$), while path compression ensures that any depth a tree does accumulate gets paid down and reused, so the expensive walks cannot recur. Neither alone gives $\alpha (n)$ (union by rank alone is $O(\log n)$ amortized, path compression alone is $O(\log n)$ amortized), but their combination collapses to inverse Ackermann. The full proof uses a subtle potential-function (amortized) argument, charging each node's cost against the steady growth of the ranks above it. The intuition to keep is that a node can be lifted closer to the root only so many times before it is the root's child, and ranks climb too slowly for that to happen often.

from collections.abc import Hashable, Iterable
from typing import Generic, TypeVar, cast

Element = TypeVar("Element", bound=Hashable)

class DisjointSetNode(Generic[Element]):
  """
    One element's node: its value, its parent link, and its rank.\n
    A node is its own parent exactly when it is the root of its set.\n
  """

  def __init__(self, value: Element) -> None:
    self.value: Element = value
    self.parent: DisjointSetNode[Element] = self
    self.rank: int = 0

  def __repr__(self) -> str:
    return f"DisjointSetNode({self.value!r})"

class UnionFind(Generic[Element]):
  """
    A collection of disjoint sets over hashable elements.\n
  """

  def __init__(self, elements: int | Iterable[Element] = 0) -> None:
    """
      Seed the structure. An int `n` creates singletons `0..n-1`;\n
      an iterable creates one singleton node per member.\n
    """
    # a seed count `n` means the elements are 0..n-1 (ints standing in for
    # Element); cast keeps the type checker happy about that substitution.
    members: Iterable[Element] = (
      cast("Iterable[Element]", range(elements))
      if isinstance(elements, int)
      else elements
    )
    # one singleton node per seeded member.
    self._nodes: dict[Element, DisjointSetNode[Element]] = {
      value: DisjointSetNode(value) for value in members
    }
    self.count: int = len(self._nodes)

  def add(self, value: Element) -> None:
    """
      Add `value` as a new singleton set if it is absent.\n
    """
    if value not in self._nodes:
      self._nodes[value] = DisjointSetNode(value)
      self.count += 1

  def _find_root(self, value: Element) -> DisjointSetNode[Element]:
    """
      The root node of `value`'s set, compressing the path on the way.\n
    """
    # first pass: climb parent links to the root of the set.
    node = self._nodes[value]
    root = node
    while root.parent is not root:
      root = root.parent

    # second pass: point every node on the path straight at the root.
    while node.parent is not root:
      node.parent, node = root, node.parent

    return root

  def find(self, value: Element) -> Element:
    """
      The representative value of `value`'s set.\n
    """
    return self._find_root(value).value

  def union(self, first: Element, second: Element) -> bool:
    """
      Merge the sets containing `first` and `second`.\n
      Returns False if they already shared a set.\n
    """
    # already in the same set: nothing to merge.
    first_root = self._find_root(first)
    second_root = self._find_root(second)
    if first_root is second_root:
      return False

    # hang the shorter tree under the taller one.
    if first_root.rank < second_root.rank:
      first_root, second_root = second_root, first_root
    second_root.parent = first_root

    # equal ranks: the merged tree grows one level taller.
    if first_root.rank == second_root.rank:
      first_root.rank += 1

    self.count -= 1
    return True

  def connected(self, first: Element, second: Element) -> bool:
    """
      Whether `first` and `second` belong to the same set.\n
    """
    return self._find_root(first) is self._find_root(second)

A worked trace: both heuristics together

For a trace of the two heuristics together, start with seven singletons $a,b,c,d,e,f,g$, each its own tree of rank $0$, and process this sequence of operations:

Union by rank governs each merge, breaking ties by keeping the first-named root.

1. $\text{Union}(a,b)$. Both rank $0$; equal ranks, so hang $b$ under $a$ and bump $a$ to rank $1$. Tree: $a\leftarrow b$.
2. $\text{Union}(c,d)$. Both rank $0$; hang $d$ under $c$, $c$ becomes rank $1$. Tree: $c\leftarrow d$.
3. $\text{Union}(a,c)$. Both roots have rank $1$; equal ranks, so hang $c$ under $a$ and bump $a$ to rank $2$. Now $a$ has children $b$ and $c$, and $c$ still has child $d$: $d$ sits at depth $2$.
4. $\text{Union}(e,f)$. Both rank $0$; hang $f$ under $e$, $e$ to rank $1$.
5. $\text{Union}(a,e)$. $a$ has rank $2$, $e$ has rank $1$; ranks differ, so hang the smaller-rank root $e$ under $a$ and no rank changes ($a$ stays rank $2$). The tree rooted at $a$ now holds all seven elements, with $d$ and $f$ at depth $2$.
6. $\text{Find-Set}(d)$. Walk $d\to c\to a$ to reach root $a$, then compress: point $d$ (and $c$, already a child of $a$) straight at $a$. The next $\text{Find-Set}(d)$ is a single hop.

Two details from this run are worth stating precisely. First, only step 1, 2, 3, 4 ever raised a rank, and each raise required merging two trees of equal rank, exactly the doubling that caps rank at ${\log }_{2}n$. Step 5 merged unequal ranks and left every rank untouched, which is the common case in practice. Second, notice that after compression $d$'s rank-based ancestor $c$ is still recorded as rank $1$ even though $c$ is now a leaf, this is why ranks are only an upper bound on height, and why the heuristic keeps the name rank rather than

Application: connectivity and minimum spanning trees

Two applications make the structure indispensable.

Connectivity. Given a graph, call $\text{Make-Set}$ on every vertex, then $\text{Union}(u,v)$ for every edge $\left\{u,v\right\}$. Afterward, $\text{Find-Set}(u)=\text{Find-Set}(v)$ holds iff $u$ and $v$ lie in the same connected component. The structure also processes online edge insertions: each new edge is one Union, and connectivity queries between insertions are each one pair of $\text{Find-Set}$ calls, both amortized $O(\alpha (n))$.

Kruskal's minimum spanning tree. Kruskal's algorithm builds a minimum spanning tree by scanning edges in increasing weight order and adding each edge unless it would form a cycle. An edge $\left\{u,v\right\}$ forms a cycle exactly when $u$ and $v$ are already connected (i.e. already in the same set), which is the disjoint-set query verbatim.⁴

Now read off the running time. Sorting the edges costs $O(m\log m)$, and since a simple graph has $m\le n^2$ edges we have $\log m\le 2\log n$, so the sort is $O(m\log n)$, and this dominates. The disjoint-set work spans $O(m)$$\text{Find-Set}$ tests and $O(n)$ $\text{Union}$s; even with only the warm-up's relabel-the-smaller scheme this is $O(m+n\log n)$, already cheaper than the sort, and with the rank/compression forest it is $O(m\alpha (n))$, effectively linear. Either way:

The lesson here is worth stating plainly: Kruskal's logic is one acyclicity test per edge, but its efficiency is entirely a property of the structure answering that test. The cycle test is the same-set query, and a good disjoint-set structure is what makes Kruskal both simple and fast.

from __future__ import annotations

from collections.abc import Hashable
from typing import Generic, TypeVar

from graph import Graph
from union_find import UnionFind

Label = TypeVar("Label", bound=Hashable)

def count_components(graph: Graph[Label]) -> int:
  """
    The number of connected components in the undirected `graph`.\n
  """
  return connected_components(graph).count

def has_cycle(graph: Graph[Label]) -> bool:
  """
    Whether the undirected `graph` contains a cycle.\n
    A cycle exists iff some edge joins two vertices already connected.\n
  """
  # a union that finds its endpoints already joined closes a cycle.
  components: UnionFind[Label] = UnionFind(graph.labels)
  for edge in graph.edges():
    if not components.union(edge.source.label, edge.target.label):
      return True

  return False

class ConnectedComponents(Generic[Label]):
  """
    An online connectivity oracle over a fixed vertex set.\n
    Vertices are fixed up front; edges arrive one at a time through\n
    `connect`, and connectivity queries answer in amortized O(alpha(n)).\n
  """

  def __init__(self, vertices: list[Label]) -> None:
    """
      Start with each vertex in its own component.\n
    """
    self._sets: UnionFind[Label] = UnionFind(vertices)

  def connect(self, first: Label, second: Label) -> bool:
    """
      Insert the edge {first, second}. Returns True if this merged two\n
      distinct components, or False if they were already connected (the\n
      edge would close a cycle).\n
    """
    return self._sets.union(first, second)

  def connected(self, first: Label, second: Label) -> bool:
    """
      Whether `first` and `second` lie in the same component.\n
    """
    return self._sets.connected(first, second)

  @property
  def count(self) -> int:
    """
      The current number of connected components.\n
    """
    return self._sets.count

  def component_of(self, vertex: Label) -> Label:
    """
      The representative label of `vertex`'s component.\n
    """
    return self._sets.find(vertex)

def connected_components(graph: Graph[Label]) -> ConnectedComponents[Label]:
  """
    Build a ConnectedComponents oracle over `graph` by unioning the\n
    endpoints of every edge.\n
  """
  # union every edge's endpoints into the oracle's vertex set.
  oracle: ConnectedComponents[Label] = ConnectedComponents(graph.labels)
  for edge in graph.edges():
    oracle.connect(edge.source.label, edge.target.label)

  return oracle

from __future__ import annotations

from collections.abc import Hashable
from typing import NamedTuple, TypeVar

from graph import Edge, Graph
from union_find import UnionFind

Label = TypeVar("Label", bound=Hashable)

class MinimumSpanningTree(NamedTuple):
  """
    The result of a Kruskal run: the chosen edges as (source, target,\n
    weight) triples, and their total weight.\n
  """
  edges: list[tuple[Hashable, Hashable, float]]
  total_weight: float

def kruskal_mst(graph: Graph[Label]) -> MinimumSpanningTree:
  """
    A minimum spanning forest of the undirected `graph`. On a connected\n
    graph this is a spanning tree with len(graph) - 1 edges; on a\n
    disconnected graph it is the union of each component's spanning tree.\n
  """
  # every vertex in its own component, edges sorted by weight ascending.
  components: UnionFind[Label] = UnionFind(graph.labels)
  candidates: list[Edge[Label]] = sorted(
    graph.edges(), key=lambda edge: edge.weight
  )

  chosen: list[tuple[Hashable, Hashable, float]] = []
  total_weight: float = 0.0

  for edge in candidates:
    source_label = edge.source.label
    target_label = edge.target.label

    # accept the edge iff its endpoints sit in different components.
    if components.union(source_label, target_label):
      chosen.append((source_label, target_label, edge.weight))
      total_weight += edge.weight

  return MinimumSpanningTree(chosen, total_weight)

from collections.abc import Hashable, Iterator
from typing import Generic, Optional, TypeVar


Label = TypeVar("Label", bound=Hashable)


class Edge(Generic[Label]):
  """
    A directed connection from `source` to `target`, carrying a weight.\n
  """

  def __init__(
    self,
    source: Vertex[Label],
    target: Vertex[Label],
    weight: float = 1.0,
  ) -> None:
    self.source: Vertex[Label] = source
    self.target: Vertex[Label] = target
    self.weight: float = weight

  def __repr__(self) -> str:
    return f"Edge({self.source.label!r} -> {self.target.label!r}, w={self.weight})"


class Vertex(Generic[Label]):
  """
    A graph vertex: a label plus the list of edges leaving it.\n
  """

  def __init__(self, label: Label) -> None:
    self.label: Label = label
    self.outgoing: list[Edge[Label]] = []

  def neighbors(self) -> list[Vertex[Label]]:
    """
      The vertices reachable from this one by a single edge.\n
    """
    return [edge.target for edge in self.outgoing]

  def edge_to(self, label: Label) -> Optional[Edge[Label]]:
    """
      The outgoing edge to the vertex with `label`, or None.\n
    """
    for edge in self.outgoing:
      if edge.target.label == label:
        return edge
    return None

  def __repr__(self) -> str:
    return f"Vertex({self.label!r})"


class Graph(Generic[Label]):
  """
    A graph of Vertex objects linked by Edge objects.\n
    Pass `directed=True` for a digraph; otherwise each `add_edge` inserts\n
    the reverse edge too.\n
  """

  def __init__(self, directed: bool = False) -> None:
    self.directed: bool = directed
    self._vertices: dict[Label, Vertex[Label]] = {}

  def add_vertex(self, label: Label) -> Vertex[Label]:
    """
      Return the vertex for `label`, creating it if it is absent.\n
    """
    # reuse the existing vertex, or mint and register a fresh one.
    vertex = self._vertices.get(label)
    if vertex is None:
      vertex = Vertex(label)
      self._vertices[label] = vertex
    return vertex

  def add_edge(
    self,
    source_label: Label,
    target_label: Label,
    weight: float = 1.0,
  ) -> None:
    """
      Connect two labels (creating either vertex as needed).\n
      Adds the reverse edge as well when the graph is undirected.\n
    """
    source = self.add_vertex(source_label)
    target = self.add_vertex(target_label)

    # link source to target, and mirror it back when undirected.
    source.outgoing.append(Edge(source, target, weight))
    if not self.directed:
      target.outgoing.append(Edge(target, source, weight))

  def vertex(self, label: Label) -> Vertex[Label]:
    """
      The vertex carrying `label` (raises KeyError if absent).\n
    """
    return self._vertices[label]

  @property
  def vertices(self) -> list[Vertex[Label]]:
    """
      Every vertex, in insertion order.\n
    """
    return list(self._vertices.values())

  @property
  def labels(self) -> list[Label]:
    """
      Every vertex label, in insertion order.\n
    """
    return list(self._vertices)

  def edges(self) -> Iterator[Edge[Label]]:
    """
      Each edge once — an undirected edge is yielded a single time.\n
    """
    # track undirected endpoint pairs so each is emitted only once.
    seen: set[frozenset[Label]] = set()

    for vertex in self._vertices.values():
      for edge in vertex.outgoing:
        # skip an undirected edge already yielded from the other endpoint.
        if not self.directed:
          endpoints = frozenset((edge.source.label, edge.target.label))
          if endpoints in seen:
            continue
          seen.add(endpoints)

        yield edge

  def __contains__(self, label: Label) -> bool:
    return label in self._vertices

  def __iter__(self) -> Iterator[Vertex[Label]]:
    return iter(self._vertices.values())

  def __len__(self) -> int:
    return len(self._vertices)

from collections.abc import Hashable, Iterable
from typing import Generic, TypeVar, cast


Element = TypeVar("Element", bound=Hashable)


class DisjointSetNode(Generic[Element]):
  """
    One element's node: its value, its parent link, and its rank.\n
    A node is its own parent exactly when it is the root of its set.\n
  """

  def __init__(self, value: Element) -> None:
    self.value: Element = value
    self.parent: DisjointSetNode[Element] = self
    self.rank: int = 0

  def __repr__(self) -> str:
    return f"DisjointSetNode({self.value!r})"


class UnionFind(Generic[Element]):
  """
    A collection of disjoint sets over hashable elements.\n
  """

  def __init__(self, elements: int | Iterable[Element] = 0) -> None:
    """
      Seed the structure. An int `n` creates singletons `0..n-1`;\n
      an iterable creates one singleton node per member.\n
    """
    # a seed count `n` means the elements are 0..n-1 (ints standing in for
    # Element); cast keeps the type checker happy about that substitution.
    members: Iterable[Element] = (
      cast("Iterable[Element]", range(elements))
      if isinstance(elements, int)
      else elements
    )
    # one singleton node per seeded member.
    self._nodes: dict[Element, DisjointSetNode[Element]] = {
      value: DisjointSetNode(value) for value in members
    }
    self.count: int = len(self._nodes)

  def add(self, value: Element) -> None:
    """
      Add `value` as a new singleton set if it is absent.\n
    """
    if value not in self._nodes:
      self._nodes[value] = DisjointSetNode(value)
      self.count += 1

  def _find_root(self, value: Element) -> DisjointSetNode[Element]:
    """
      The root node of `value`'s set, compressing the path on the way.\n
    """
    # first pass: climb parent links to the root of the set.
    node = self._nodes[value]
    root = node
    while root.parent is not root:
      root = root.parent

    # second pass: point every node on the path straight at the root.
    while node.parent is not root:
      node.parent, node = root, node.parent

    return root

  def find(self, value: Element) -> Element:
    """
      The representative value of `value`'s set.\n
    """
    return self._find_root(value).value

  def union(self, first: Element, second: Element) -> bool:
    """
      Merge the sets containing `first` and `second`.\n
      Returns False if they already shared a set.\n
    """
    # already in the same set: nothing to merge.
    first_root = self._find_root(first)
    second_root = self._find_root(second)
    if first_root is second_root:
      return False

    # hang the shorter tree under the taller one.
    if first_root.rank < second_root.rank:
      first_root, second_root = second_root, first_root
    second_root.parent = first_root

    # equal ranks: the merged tree grows one level taller.
    if first_root.rank == second_root.rank:
      first_root.rank += 1

    self.count -= 1
    return True

  def connected(self, first: Element, second: Element) -> bool:
    """
      Whether `first` and `second` belong to the same set.\n
    """
    return self._find_root(first) is self._find_root(second)

Lower bounds, and where union-find runs

Two threads extend the textbook treatment, one theoretical and one practical.

The bound is tight, and $\alpha (n)$ is unavoidable. It is natural to suspect the inverse-Ackermann factor is an artifact of a loose analysis, that a cleverer argument would prove $O(m)$. It cannot. Fredman and Saks (1989) proved a matching lower bound: in the cell-probe model, any data structure for the disjoint-set problem must spend $\Omega (m\alpha (n))$ time on some sequence of $m$ operations. So Tarjan's analysis is not merely the best known, it is the best possible, and $\alpha (n)$ is an intrinsic feature of the problem, not of the algorithm. The function itself is the inverse of the fast-growing Ackermann function $A(k,j)$, whose rows climb from addition ($A(1,\cdot )$) to multiplication, exponentiation, towers of exponents, and beyond; $\alpha (n)$ asks how many rows up you must go before the values exceed $n$, and the answer is at most $4$ for any $n$ that could be written down.

Beyond the merge-only model. Plain union-find handles only incremental connectivity, edges arrive and components merge, never split. Two extensions answer harder queries. A union-find with rollback (used inside offline dynamic-connectivity algorithms) forgoes path compression, so that unions can be undone in a stack discipline; it keeps $O(\log n)$ per operation but supports a decremental or fully offline stream of edge insertions and deletions. And the Euler-tour / link-cut structures solve fully dynamic connectivity, edges inserted and deleted online, in $O({\log }^{2}n)$ amortized time, well outside what parent pointers can do. In practice, the merge-only structure is enough for the dominant applications: Kruskal's MST, connected-component labeling in image segmentation (the Felzenszwalb–Huttenlocher segmenter is union-find on a pixel graph, edges scanned by weight exactly as in Kruskal), percolation simulations, and the type-inference union of equivalence classes in compilers.⁵

Takeaways

• The disjoint-set ADT — $\text{Make-Set}$, $\text{Find-Set}$, Union — maintains a partition under merges and answers same group? by comparing representatives.
• A labels + relabel-the-smaller warm-up already costs only $O(n\log n)$ total: each element is relabeled $\le {\log }_{2}n$ times because its set doubles whenever it moves. This doubling argument is the seed of union by rank.
• The forest representation stores each set as a tree of parent pointers whose root is the representative; $\text{Find-Set}$ walks to the root, Union links two roots, turning the warm-up's $O(\text{size})$ relabel into one $O(1)$ pointer move.
• Union by rank keeps trees short (attach shorter under taller), and path compression flattens each $\text{Find-Set}$ path to point straight at the root.
• Together they give $O(\alpha (n))$ amortized time per operation — inverse Ackermann, so $\le 4$ for any realistic $n$, i.e. effectively constant.
• It powers connectivity queries and Kruskal's MST, where the same-set test doubles as the cycle test. Kruskal runs in $O(m\log n)$, with the sort, not the union-find, as the bottleneck.
• The unifying theme: clever data structures are what make algorithms fast. Kruskal's logic is one line; all of its speed comes from the disjoint-set structure underneath.