num::basic_disjoint_set¶

Defined in header <structures/containers/disjoint_set.hpp>

template <std::integral Index = num::idx>
class basic_disjoint_set;

Disjoint-Set forest data structure supporting near O(1) amortized operations.

Template parameters¶

Index: Integer type used for vertex/element indices (e.g. num::idx, uint32_t, int).

member	description
`using index_type = Index`
`explicit basic_disjoint_set(Index n = 0)`	Construct a disjoint-set structure with n singleton sets: {0}, {1}, ..., {n-1}.
`Index find(Index u)`	Find the representative root of the set containing element u with path compression.
`Index find(Index u) const`	Find representative root (const view without mutation).
`bool unite(Index u, Index v)`	Unite the sets containing elements u and v.
`bool connected(Index u, Index v)`	Check whether elements u and v belong to the same connected component.
`Index component_size(Index u)`	Return the number of elements in the component containing element u.
`Index count() const noexcept`	Return the total number of disjoint components remaining.
`Index size() const noexcept`	Return the total number of elements.
`void reset(Index n = 0)`	Reset the structure back to n singleton sets.
`array<array<Index>> components()`	Return all connected components as lists of element indices.