Module advanced_collections::disjoint_set
source · Expand description
Disjoint-set is a set of elements paritioned in a collection of non-overlapping subsets.
This data structure is also known as union-find or merge-find set. This implementation supports path compression and union by rank features that make typical operations much more efficient.
More: https://en.wikipedia.org/wiki/Disjoint-set_data_structure
Complexity
|Metric | Complexity | -––––––––––|————| | Create a new subset | O(1) | | Union | ≈ O(1) | | Search | ≈ O(1) | | Memory | O(n) |
Structs
where α() - very slowly growing function. α(n) < 4 for any reasonable n.
Therefore O(α(n)) ≈ O(1).
Type Definitions
A faster but less safe version of DisjointSet.