2.2.6 并查集

并查集（Disjoint set或者Union-find set）是一种树结构，常用于处理一些不相交集合（Disjoint Sets）的查询（Find）及合并（Union）问题，包含两种基本操作：

☢ Find(x)——查询元素x属于哪一个子集。

☢ Union(x, y)——将元素x和元素y所在的子集合并成同一个集合。

在图2-26中，查询操作Find(D)和Find(F)分别返回对应树的根结点A和H，合并操作Union(D, F)则把D和F所在的两棵树合并，如右图所示。

图2-26 并查集的Find和Union操作

并查集森林将每个集合以树表示，树中的每个结点保存着到其父结点的引用，根结点没有父结点，其引用赋值为-1。每个集合选定一个固定的元素作为该集合的代表，称为代表元素，代表元素则用于标识整个集合。每个集合的代表元素即集合的根结点。并查集森林可以采用双亲表示法，如图2-27所示，father数组下标代表元素的序号，其值表示父结点的序号。元素4的父结点是5，因此 father[4]=5。

图2-27 集合树的双亲表示法

根据并查集森林的定义，我们可以设计Find(x)算法，即从结点x开始不断向上遍历，直到根结点为止。显然，该算法的时间复杂性是线性的。

程序2-7 查询操作Find算法实现

类似地，我们也可以设计Union(x, y)算法，即先查询x所在集合的代表元素xRoot，查询y所在集合的代表元素yRoot，如果代表元素不相同，则把yRoot指向xRoot。

程序2-8 合并操作Union算法实现

这是并查集森林最基础的表示方法以及Find和Union操作。注意，在数据不平衡时，大量的Union操作可能导致集合树的深度比较深，Find操作的效率降低。