File UnionFind.h

↰ Parent directory (ADS/mfset)

The MFSET of section 10.2 engineered, beyond the book [see File MFSet.h]: the forest of the parents in one vector of integers, where a root keeps minus the size of its tree instead of a parent, so that the union by size needs no second vector and a find() touches one array; find() halves the path (each node on the way is made a child of its grandparent), which needs a single pass, no recursion and no stack, and keeps the bound of the compression with the union by size (Tarjan and van Leeuwen): a sequence of :math:` m geq n ` operations on n elements takes.

Definition (ADS/mfset/UnionFind.h)

Detailed Description

:math:`[

O( n + m , alpha( m , n ) ) ,

` :math:` alpha ` the inverse of the function of Ackermann, at most 4 for any n that fits a computer; a tree of root r has at least :math:` 2^h ` nodes, h its height, so that a single find() is :math:` O( log n ) ` in the worst case. The space is 4 n bytes. Patwary, Blair and Manne found the union by size or rank with halving among the fastest variants, close to the splicing of Rem, which the benchmark of this library finds slower up to :math:` 10^6 ` elements. It is the union-find of the algorithms of Kruskal and of the connected components.

The contracts [see File Contract.h]: n >= 0, the elements are in [ 0 , n ); the invariant is that the parents make a forest of count() trees whose roots hold minus their sizes. The operations are defined in UnionFind.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 10.2, https://algoritmicamente.it/materiali/libro/capitoli/cap10.pdf

    1. Tarjan, J. van Leeuwen, Worst-case analysis of set union algorithms, Journal of the ACM 31(2), 245-281, 1984, doi:10.1145/62.2160

      1. Patwary, J. Blair, F. Manne, Experiments on union-find algorithms for the disjoint-set data structure, Proceedings of SEA, LNCS 6049, 411-423, 2010, doi:10.1007/978-3-642-13193-6_35

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes

Enums

Typedefs