tpl_union.H File Reference

Union-Find (Disjoint Set Union) data structure. More...

#include <tpl_dynArray.H>
#include <tpl_dynSetTree.H>
#include <limits>
#include <stdexcept>
#include <ah-errors.H>

Include dependency graph for tpl_union.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Fixed_Relation
	Binary relation between a set of integers. More...
class	Relation
	Binary relation between a set of integers. More...
class	Relation_T< T, Compare >
	Binary relation between a set of items. More...
struct	Relation_T< T, Compare >::Pair
struct	Relation_T< T, Compare >::Cmp

Detailed Description

Union-Find (Disjoint Set Union) data structure.

Efficiently tracks partitioning of elements into disjoint sets. Supports near-constant time union and find operations.

Features

• Path compression for find
• Union by rank
• Inverse Ackermann amortized complexity

Complexity: O(α(n)) amortized per operation

See also

tpl_components.H Graph connectivity using Union-Find

Author

Leandro Rabindranath León

Definition in file tpl_union.H.