并查集

在计算机科学中，并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。有一个联合查找算法（union-find algorithm）定义了两个用于此数据结构的操作：

• Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
• Union：将两个子集合并成同一个集合。
  由于支持这两种操作，一个不相交集也常被称为联合-查找数据结构（union-find data structure）或合并-查找集合（merge-find set）。其他的重要方法 ，MakeSet 用于创建单元素集合。有了这些方法 ，许多经典的划分问题可以被解决。

为了更加精确的定义这些方法，需要定义如何表示集合。一种常用的策略是为每个集合 选定一个固定的元素，称为代表 ，以表示整个集合。接着 Find(x) 返回 x 所属集合的代表，而 union 使用两个集合的代表作为参数。

并查集森林

并查集森林是一种将每个集合以树表示的数据结构，其中每一个节点保存着到它的父节点的引用。

在并查集森林中，每个集合的代表即是集合的根节点。“查找”根据 其父节点的引用向根行进直到到底树根。“联合”将两棵树合并在一起，这通过将一颗树的根连接到另一颗树的根。

这是并查集森林的最基础的表示方法，这个方法不会比链表 法好，这是因为创建的树可能会严重性不平衡；然而，可以用两种方法优化。

1. “按秩合并”，即总是将更小的树连接到更大的树上。
2. “路径压缩”，是一种在执行“查找”时扁平化树结构的方法。

主要操作

• 合并两个不相交集合
• 判断两个元素是否属于同一个集合

并查集的优化

• 路径压缩
• Rank 合并

复杂度分析

• 时间复杂度：同时使用路径压缩、按秩（Rank）合并优化的程序每个操作的平均时间为 O(a(n)) （一个极小的常数）, a(n) 是 n = f(x) = A(x, x) 的反函数，A 是急速增加的阿克曼函数。
• 空间复杂度：O(n)。