并查集

Posted on | In
记录了我对并查集的学习笔记

并查集

并查集主要用来解决元素分组的问题。它支持两种操作：

  • 合并（Union）：把两个不相交的集合合并成一个集合。
  • 查询（Find）：查询两个元素是否在同一个集合中。

并查集的核心思想是用集合中的一个元素代表整个集合。

image-20240227011735365

并查集是一个树状的结构，要寻找集合中的代表元素，只需要向上一层一层访问父节点。

通过以上知识，可以先写出最简单版本的并查集代码。

初始化

1
2
3
4
5
6
7
8
int fa[MAXN];
void init (int n)
{
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
}

使用数组fa来存储每个元素的父节点。

查询

1
2
3
4
5
6
7
int find(int x)
{
    if(fa[x]==x)
        return x;
    else
        return find(fa[x]);
}

使用递归一层一层访问父节点，直到根节点。通过判断两个元素的根节点是否一致，得出他们是否属于同一集合。

合并

1
2
3
4
void merge(int i, int j)
{
    fa[find(i)]=find(j);
}

路径压缩

最简单的并查集效率是比较低的。merge（2，4）会使得树变成一条长链。随着链的增长，从底部找到跟节点将越来越慢。

image-20240227015949913

最好能够使得每个元素到根节点的距离尽可能短，距离只有1。

image-20240227020533562

为了实现路径压缩，只需要在查询的过程中，把沿途的每个节点的父节点都设为根节点。

1
2
3
4
5
6
7
8
9
10
// 路径压缩
int find(int x)
{
    if(fa[x]==x)
        return x;
    else{
        fa[x]=find(fa[x]); // 父节点设为根节点
        return fa[x];
    }
}

按秩合并

虽然经过了路径压缩这一优化，但并查集的结构仍然可能比较复杂。因为路径压缩只在查询时进行，而且只压缩一条路径。对于以下这种情况：

image-20240227023419143

merge（7，8）有两种选择：把7的父节点设为8，或把8的父节点设为7。

显然后者好。要是把7的父节点设为8，会使树的深度增加1，每个节点寻找根节点的路径都会变长。虽然有路径压缩这一优化方案，但优化方案本身也是耗时的。如果把8的父节点设为7，就不会影响到原来的树结构。

所以，应该把简单的树往复杂的树上合并。

用一个数组depth记录每个根节点对应的树的深度。合并时比较两个根节点的depth，把depth小的往depth大的合并。

1
2
3
4
5
6
7
8
9
10
11
12
13
void merge(int i, int j)
{
    int x=find(i), y=find(j);
    if(depth[x]<=depth[y]){
        fa[x]=y;
    }
    else{
        fa[y]=x;
    }
    if(depth[x]==depth[y] && x!=y){
        depth[y]++;  //如果两个根节点深度相同，合并后的根节点深度+1
    }
}

参考

https://zhuanlan.zhihu.com/p/93647900