并查集 | clorf's blog

并查集( $\text{Disjoint-Set}$ )是一种较为简单的数据结构，主要用于解决连通性及动态维护集合的一些问题。

一、操作

并查集主要有两个操作：

查询( $\text{Get}$ )，查询一个元素属于哪个集合；
合并( $\text{Merge}{}$ )，把两个集合合并成一个大集合。

那怎样具体实现呢？

二、实现

对于具体实现，我们采用”代表元”法，就是为每个集合选择一个固定的元素，作为整个集合的”代表”。

然后就是定义归属关系的表示方法。有两种思路：

第一种思路就是维护一个数组 $f$ ，用 $f[x]$ 保存元素 $x$ 所在集合的代表。这种方法查询很快，但是合并时对于 $f$ 值要做大量修改，不好实现且效率低下。
第二种思路就是使用一颗树形结构存储每个集合，树根就是代表元，树上每个节点就是每一个集合中的元素。整个并查集就是一个森林。此时我们就相当于维护一个树形结构，用一个 $father$ 数组即可，合并时只用连接树根，即 $father[root1]=root2$ 。但在查询时，要递归查询一个元素的 $father$ 值，一直到树根。

很明显选择第二种思路。

三、优化

由于第二种思路在查询代表元时效率较低，有什么优化呢？

有以下两种优化：

(1). 路径压缩

我们知道第一种思路的查询速度很快，我们可以将两种思路结合起来。很明显，查询元素 $x$ 的代表元只与树根 $root$ 与元素 $x$ 有关，至于树长什么样与之无关。这意味着下图中两颗树是等价的。

很明显，右边那张图查询起来要比左边那张图要快，因为右边的树的深度比左边的树的深度小。因此，我们可以在每次执行 $Get$ 操作的同时，把访问的每个树节点(也就是所查询元素的祖先节点)都直接指向树根，这种那个优化方法叫做路径压缩。采用这种优化方法，每次 $Get$ 操作的均摊复杂度为 $O(log\ N)$ 。

(2). 按秩合并

秩是指集合的大小，即树的元素个数，按秩合并其实就是按照树的元素个数大小一次合并，即把秩较小的树的树根合并到秩较大的树的树根上，这样能使树的每一条分支的深度尽量平均。这其实也被称为启发式合并。它是数据结构中合并的一个重要思想，本质就是将小的结构接在大的结构上。这样一来，把所有结构全都合并起来，增加的代价不超过 $N\ log\ N$ ，所以单独采用按秩合并的并查集，均摊复杂度也为 $O(log\ N)$ 。

一般并查集只用路径压缩就可以了，但如果同时采用两种方法，复杂度可进一步降低到 $O(\alpha(N))$ 。中间的那个函数为反阿克曼函数，可近似为一个常数。

四、具体实现

(1). 并查集的存储

使用 $fa$ 数组存储父节点。

int fa[SIZE];

(2). 并查集的初始化

初始化时，每个节点的父节点是他自己。

for(int i=1;i<=n;i++)
    fa[i]=i;

(3). `Get` 操作

递归至树根返回，否则继续递归。

int getfa(int x)
{
    if(fa[x]==x)
        return x;
    return fa[x]=getfa(fa[x]);//路径压缩
}

(4). `Merge` 操作

合并集合就是把一棵树的树根作为另一棵树的树根的子节点。

int merge(int a,int b)
{
    int x=getfa(a);
    int y=getfa(b);
    if(x!=y)
        fa[x]=y;
}

五、边带权的并查集

并查集是一个树形结构，所以我们可以在树上每条边维护一个权值，即维护一个数组 $d$ ，用 $d[x]$ 保存节点 $x$ 到父节点 $fa[x]$ 之间的权值。但是在每次路径压缩时，由于父节点发生了变化，所以 $d[x]$ 也要随时更新，这样就可以做到实现一个边带权的并查集。

例如 $d[x]$ 维护的是到根节点的路径长：

int getfa(int x)
{
    if(fa[x]==x)
        return x;
    int root=getfa(fa[x]);
    d[x]+=d[fa[x]];
    return fa[x]=root;
}

六、扩展域

当并查集传递的关系比较复杂时，就要用到扩展域。

例如，一个元素具有 $n$ 种属性，并且传递的关系也有 $n$ 种，我们就可以将一个元素分成 $n$ 个只有一种属性的节点，将这些不同的属性当作普通并查集一一传递，这就是扩展域的本质，即用扩大的空间来传递信息。

例如两个元素分别为 $x$ ， $y$ ，它们各自都有两种属性，在传递关系时我们可以这样：

int main()
{
	int x,y;
	int x1=x,x2=x+n;//x1为x的第一种属性，x2为x的第二种属性
	int y1=y;y2=y+n;//同上，一样的道理
	fa[getfa(x1)]=y1;
	fa[getfa(x2)]=y2;//分别传递两种信息
}