dsu-tree

一种非侵入式的 并查集树 数据结构实现，用 Rust 编写。

并查集树

并查集 数据结构，或 DSU，或 并查集数据结构，或 归并-查找集，是一种存储不相交集合集合的数据结构。它提供了添加新集合、合并集合（相当于用它们的并代替集合）和查找集合代表成员的操作。DSU 在实现如 最小生成树 等算法时非常有用。

DSU 可以通过使用 并查集树 来以极高的效率实现。并查集树实际上是一棵森林，其中每个节点代表一个集合，每棵树代表合并在一起的集合的并集。三个 DSU 操作可以如下实现

• 添加新集合：简单。只需将新节点添加到森林中即可。新节点本身就是森林中的一棵树，表示它们尚未与其他集合合并。
• 合并集合：要合并两个对应的节点分别为 A 和 B 的集合，我们只需将 A 的父节点改为 B 即可。在实际实现中，需要考虑一些特殊情况，如将集合合并到自身。
• 查找集合的代表成员：并查集树中的每棵树代表一个集合。集合的代表成员可以选择为树根节点对应的集合的代表成员。

本库

本库不是实现并查集数据结构，而是提供了底层并查集树数据结构的实现。

关于此库的使用，请参阅 文档。

许可

此库在 MIT 许可证 下开源。