Struct DisjointSet 

pub struct DisjointSet { /* private fields */ }

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

This is the complete version of the skeleton from graph-collections. Path compression flattens the tree during every Self::find call, giving amortised O(α(n)) per operation where α is the inverse Ackermann function — effectively constant for all practical inputs.

Examples

use graph_spanning::DisjointSet;

let mut ds = DisjointSet::new(5);
assert_eq!(ds.count(), 5);

ds.union(0, 1);
ds.union(2, 3);
assert!(ds.connected(0, 1));
assert!(ds.connected(2, 3));
assert!(!ds.connected(0, 2));
assert_eq!(ds.count(), 3);

ds.union(1, 3); // merges the two groups
assert!(ds.connected(0, 3));
assert_eq!(ds.count(), 2);

Implementations

impl DisjointSet

pub fn new(n: usize) -> Self

Creates a new Union-Find with n elements, each in its own set.

Elements are indexed 0..n.

Examples

use graph_spanning::DisjointSet;

let ds = DisjointSet::new(4);
assert_eq!(ds.count(), 4);

pub fn find(&mut self, x: usize) -> usize

Finds the representative (root) of the set containing x.

Applies path compression: every node on the path to the root is re-pointed directly to the root, flattening the tree for future calls.

Panics

Panics if x >= n (out of bounds).

Examples

use graph_spanning::DisjointSet;

let mut ds = DisjointSet::new(3);
ds.union(0, 1);
// After union, both 0 and 1 share the same representative.
assert_eq!(ds.find(0), ds.find(1));

pub fn union(&mut self, x: usize, y: usize) -> bool

Merges the sets containing x and y.

Uses union by rank: the root of the smaller-rank tree is attached to the root of the larger-rank tree, keeping the tree shallow.

Returns true if x and y were in different sets (a merge occurred), or false if they were already in the same set.

Panics

Panics if x or y is out of bounds.

Examples

use graph_spanning::DisjointSet;

let mut ds = DisjointSet::new(3);
assert!(ds.union(0, 1));  // merged
assert!(!ds.union(0, 1)); // already connected

pub fn connected(&mut self, x: usize, y: usize) -> bool

Returns true if x and y are in the same set.

Panics

Panics if x or y is out of bounds.

Examples

use graph_spanning::DisjointSet;

let mut ds = DisjointSet::new(4);
ds.union(0, 1);
ds.union(1, 2);
assert!(ds.connected(0, 2)); // transitive
assert!(!ds.connected(0, 3));

pub fn count(&self) -> usize

Returns the current number of disjoint sets.

Starts at n and decreases by 1 for every successful Self::union call.

Examples

use graph_spanning::DisjointSet;

let mut ds = DisjointSet::new(4);
assert_eq!(ds.count(), 4);
ds.union(0, 1);
assert_eq!(ds.count(), 3);

Trait Implementations

impl Clone for DisjointSet

fn clone(&self) -> DisjointSet

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for DisjointSet

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.