|
| | UnionFind (std::size_t n) |
| | Construct n singleton components numbered [0, n).
|
| Idx | find (Idx x) noexcept |
| | Root of the component containing x, with path compression applied.
|
| bool | unite (Idx a, Idx b) noexcept |
| | Merge the components containing a and b.
|
| bool | sameComponent (Idx a, Idx b) noexcept |
| | Whether a and b share a component.
|
| std::size_t | countComponents () const noexcept |
| | Current number of distinct components.
|
| std::size_t | size () const noexcept |
| | Total number of elements under management (fixed at construction).
|
| std::size_t | componentSize (Idx root) const noexcept |
| | Population of the component whose root is root.
|
template<class Idx = std::uint32_t>
class clustering::UnionFind< Idx >
Disjoint-set-union with iterative path compression and union-by-rank.
Stores n elements initially as singleton components. find compacts the path from x to its root in two passes so recursion depth never grows with n – the recursive one-pass form blows the default stack at n = 1M. unite merges components by attaching the shorter tree under the taller, keeping worst-case tree depth at O(log n) even without compression.
- Template Parameters
-
| Idx | Unsigned integer index type; defaults to uint32_t. Use uint64_t only when n may exceed 2^32. |
Definition at line 22 of file dsu.h.
template<class Idx = std::uint32_t>
Population of the component whose root is root.
The caller must pass a root index (typically obtained from find); passing a non-root is undefined by contract. Size is maintained at the root on every unite – when trees merge, the winning root accumulates the losing root's size so the figure stays accurate without a tree walk at query time.
- Parameters
-
| root | Root index as returned by find. |
- Returns
- Number of elements under
root's component.
Definition at line 132 of file dsu.h.
template<class Idx = std::uint32_t>
Root of the component containing x, with path compression applied.
Two-pass iterative compression: first walk to the root, then rewalk from x setting each visited node's parent to the root. The iterative form survives n = 1M inputs where the recursive form would overflow the stack.
- Parameters
-
| x | Element index; must satisfy x < size(). |
- Returns
- Root index of
x's component.
Definition at line 47 of file dsu.h.
template<class Idx = std::uint32_t>
Merge the components containing a and b.
Attaches the shorter tree under the taller; when the two ranks tie, a's root becomes the new root and its rank is bumped. No-op if a and b are already in the same component.
- Parameters
-
| a | First element index. |
| b | Second element index. |
- Returns
true if the call actually merged two distinct components, false if they were already joined.
Definition at line 73 of file dsu.h.
1.16.1