Disjoint Set - 并查集

并查集

拥有$n$个元素的集合$s = [ x_0, x_1, x_2, \cdots , x_{n-1} ]$分为两个家庭。每个家族只有唯一一个祖先，相同家庭的元素拥有相同的祖先。因此集合$s$中的每个元素的祖先只有$2$种可能。并查集是一种适合元素分类的高效树形数据结构，支持快速分类和查询。

设$father(x)$为$x$的父节点，设$ancestor(x)$为$x$的祖先节点。当$father(x) = x$时称$x$为祖先节点。

对于拥有$10$个成员的集合$s = [ 0,1,2,3,4,5,6,7,8,9 ]$，将其分成两个家庭$A$和$B$。初始时令每个成员的父亲都是自己，如图所示：

当声明$2$个成员$x_i$和$x_j$（$x_i \le x_j$）属于同一家庭，令$x_i$的节点祖先为$x_j$的父亲（也可以反过来），即$father(x_j) = ancestor(x_i)$。这样的操作会使元素$x_j$更接近祖先节点，从而缩短了递归向上查找的路径长度，该操作也称为压缩路径。

下面对上图中的集合$s$进行具体演示：

$(1)$声明$0$和$4$属于同一家庭，设置$father(4) = ancestor(0) = 0$；

$(2)$声明$1$和$9$节点属于同一家庭，设置$father(9) = ancestor(1) = 1$；

$(3)$声明$0$和$2$节点属于同一家庭，设置$father(2) = ancestor(0) = 0$；

$(4)$声明$1$和$3$节点属于同一家庭，设置$father(3) = ancestor(1) = 1$；

$(5)$声明$3$和$5$节点属于同一家庭，设置$father(5) = ancestor(3) = 1$；

$(6)$声明$6$和$8$节点属于同一家庭，设置$father(8) = ancestor(6) = 6$；

$(7)$声明$2$和$6$节点属于同一家庭，设置$father(6) = ancestor(2) = 0$；

$(8)$声明$1$和$7$节点属于同一家庭，设置$father(7) = ancestor(1) = 1$；

合并两节点$x$和$y$时，根据固定规则设置$father(y) = ancestor(x)$（或者相反）；查询节点$x$的祖宗节点时，若$father(x) \neq ancestor(x)$则设置$father(x) = ancestor(x)$。并查集的分类、查询操作的时间复杂度接近$O(1)$。

源码

DisjointSet.h

DisjointSet.cpp

测试

DisjointSetTest.cpp