gtopt::DisjointSetUnion class
#include <gtopt/bus_island.hpp>

Disjoint Set Union (Union-Find) with path compression and union by rank.

Each element is identified by a contiguous index in [0, n). All operations are amortised O(α(n)) ≈ O(1).

Constructors, destructors, conversion operators

DisjointSetUnion(std::size_t n) explicit
Construct a DSU with n singleton sets.

Public functions

auto find(std::size_t x) -> std::size_t -> auto
Find the representative (root) of the set containing x.
auto size() const noexcept -> std::size_t -> auto
Number of elements.
auto unite(std::size_t x, std::size_t y) -> bool -> auto

Function documentation

auto gtopt::DisjointSetUnion::unite(std::size_t x, std::size_t y) -> bool

Returns true if the two sets were different (and have been merged).

Merge the sets containing x and y.