A Disjoint-Set data structure (aka Union-Find w/ Rank)
What is Union-Find?
Suppose you have a collection S
of elements e1
, e2
, ...
, en
, and wish to group them into different collections using operations:
- "put
ei
andej
into the same group" (union), - "give me a representative of the group
ei
belongs to" (find).
Then a Union-Find data structure helps to store the underlying groups very efficiently and implements this API.
(Some) Applications
-
Detect Cycles in Graph: Given a graph
G
, we can put the endpoints of edges into the same group (same connected component) unless there is a pair of endpoints(ei, ej)
that share a group representative. If that happens, there was already a path existing between them, and adding this edge will add multiple paths, which cannot be the case for acyclic graphs. -
Number of connected components in Graph: Given a graph
G
, put the endpoints of edges into the same group (same connected component). Once all nodes are exhausted, the number of groups formed is the number of connected components inG
.
Some interesting lecture notes regarding Union-Find.
Usage
Setup
In Cargo.toml
, add this crate as a dependency.
[]
= { = "0.1" }
API
Example 1
Task: Create a UnionFind data structure of arbitrary size that contains usize
at its elements.
Then, union a few elements and capture the state of the data structure after that.
Solution:
use ;
use HashSet;
Example 2
Task: Create a UnionFind data structure of size at least 10
, that contains u16
at its elements.
Note: The size business only helps for reducing the number of memory reallocations required. Therefore, it is not too special and is totally optional.
Solution:
// Create a UnionFind data structure of a fixed size that contains subsets of u16.
let mut uf2 = with_capacity;
println!;