union_find

支持并查集森林数据结构的并查集算法实现。

这个包注重易用性和简洁性。

背景/上下文

1. 维基百科文章：并查集数据结构

入门指南

在您的 Cargo.toml 中将 union-find-rs 指定为一个依赖项。

[dependencies]
union-find-rs = "^0.2"

1. 将以下内容添加到您的 .rs 文件的顶部

   1. use union_find_rs::prelude::*;
      

2. 查看 UnionFind 特性以了解并查集的核心操作
3. 查看 DisjointSets 结构以了解 UnionFind 的一个实现

示例

use std::collections::HashSet;
use union_find_rs::prelude::*;

let mut sets: DisjointSets<usize> = DisjointSets::new();

sets.make_set(1).unwrap();
sets.make_set(4).unwrap();
sets.make_set(9).unwrap();

sets.union(&1, &4).unwrap();

// the disjoint sets as a vector of vectors
let as_vec: Vec<HashSet<usize>> = sets.into_iter().collect();

// there should be 2 disjoint sets, where one of them only contains `9` and the other one
// only contains `1` and `4`
assert_eq!(as_vec.len(), 2);
assert!(
    as_vec
        .iter()
        .any(|set| set == &vec![9].into_iter().collect::<HashSet<usize>>())
);
assert!(
    as_vec
        .iter()
        .any(|set| set == &vec![1, 4].into_iter().collect::<HashSet<usize>>())
);