前言: 并查集作为算法中的一个简单知识点,在实际问题上也有一定的应用.相比于其他的复杂算法(图论，动态规划和红黑树等),更容易被初学者理解和掌握.本文将介绍并查集的基础知识以及它在实际问题中的应用,希望对正在学习此知识点的学生有所帮助.

引入:

并查集,顾名思义就是具有合并,查找功能的集合,它实际上是一种树型结构.它的功能分别由union_set()和find_set()两个函数来实现.那么它们各自的功能具体要如何实现以及如何在实际上进行应用呢?为了方便理解,我们通过一个例题来讲解. alt

[链接https://ac.nowcoder.com/acm/contest/9983/G]

分析上面例题,我们可以知道只要求出有多少个朋友集群,用集群中ai的最大值与集群的总人数相乘就得到这个集群需要的苹果数,再让各个集群需要的苹果数累加即得最后的答案.那么问题的重心就转移到如何构建朋友集群.我们对每一个人进行编号(0～n),然后定义一个pre[]数组,pre[x]表示x的父节点,例如pre[10]=5表示10号的父节点是5号.初始时,每个人的父节点都是自己本身.那么我们令pre[x]=y就相当于实现了x和y的连接.当有人要加入到集群中,只需要找到集群树的根节点,让根结点与之相连即可(此方法同样使用于集群与集群的连接). 代码实现如下:

int union_set(int a,int b)
{
	int fa=find_set(a);		//查找a的根节点
    int fb=find_set(b);		//查找b的根节点
    if(fa!=fb) pre[fa]=fb;		//若a,b不在同一棵树上,则进行合并
}

至此我们完成了合并的功能,对于查找节点的根节点,我们只需要逐层向上,直到发现一个节点满足条件pre[x]==x即可; 代码实现如下:

int find_set(int x)
{
	while(pre[x]!=x) 
    	x=pre[x];		//不满足根节点的条件,则往上层查找
    return x;
}

优化: ①查找优化:分析上面查找代码我们不难发现，每次查找结点的根结点效率依赖于树的深度。由于我们没有在合并时具体规定谁是谁的父节点，这容易造成树的退化。最好情况下是n叉树，此时查找一个结点的父节点最多需要两次,最坏情况下退化成链表,查找复杂度为O(n).我们需要尽可能的维持树的结构为n叉树,根据上面的代码我们已经求出了树的根节点位置,则只需要将x到根节点路径上所有点的pre(父节点)都设为根节点即可;代码实现如下:

int find_set(int x)
{
	int n=x,newx;
	while(pre[x]!=x) 
    	x=pre[x];
    while(pre[n]!=n){	//查找优化,经过前一步操作此时的x即根节点
    	newx=pre[n];
        pre[n]=x;	//将路径上所有节点的父节点都设置成根节点
        n=newx;
    }
    return x;
}

②合并优化:之前我们就说过,我们并没有明确指出谁是谁的父节点,而这很可能导致树的退化,因此我们有必要在合并时明确一下连接规则.关于规则的制订我们可以从减小树的深度方面入手.假设现在有一棵深度为n的树,当插入单个节点时,我们很容易想到将它连接到根节点上,那么合并后树的深度依旧为n,当将两棵树合并为一棵时,我们需要比较两棵树的高度,若深度相同,最终树的深度为n+1,否则合并后的高度为MAX(n,m)(假设另一棵树深度为m).这样合并后的树的深度就能控制在最小,提升了后期查找的速度.为完成这个功能我们需要定义一个deep[]数组来存放以每个节点为根节点的树的深度.代码实现如下:

int deep[1000]  //具体大小根据题目数据大小而定
int union_set(int a,int b)
{
	int fa=find_set(a);
    int fb=find_set(b);
    if(fa!=fb){
    	if(deep[fa]==deep[fb]){		//若深度相同,最终合并后树的深度加一
        	deep[fa]++;
            pre[fb]=fa;
        }
        else{
        	deep[fa]>deep[fb]?pre[fb]=fa:pre[fa]=fb;
        }
    }
}

到此我们介绍完了并查集的基础知识和代码优化,例题的完整代码如下:

#include<bits/stdc++.h>

using namespace std;
#define sc(x) scanf("%d",&x)
#define pr(x) printf("%lld\n",x)
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
const int mod=1000000007;
int tang[1000010];		//用于记录第i个同学想要的糖果数
int s[1000010];		//pre[]数组
int find_set(int x)
{
    int nx=x,n;
    while(s[x]!=x) x=s[x];
    while(s[nx]!=nx){
        n=s[nx];
        s[nx]=x;
        nx=n;
    }
    return x;
}
void union_set(int a,int b)		//针对这题不需要进行合并优化即可通过
{
    a=find_set(a);
    b=find_set(b);
    if(tang[a]>tang[b]) tang[b]=tang[a];
    if(a!=b) s[a]=s[b];
}
int main() {
    int n,m;
    sc(n);sc(m);
    for(int i=1;i<=n;i++){
        sc(tang[i]);
        s[i]=i;			//初始时每个节点的父节点为自己本身
    }
    int a,b;
    for(int i=1;i<=m;i++){
        sc(a);sc(b);
        union_set(a,b);
    }
    long long sum=0;
    for(int i=1;i<=n;i++) sum+=tang[find_set(i)];
    printf("%lld\n",sum);
    return 0;
}

以上就是本人对并查集的理解,在写此博客前也看过一些关于并查集的文章,在此也分享一下本人认为优秀的文章

文章链接

不清楚通过上面的讲解,大家是否真正掌握并查集的使用了呢?这里有道相关题目,大家趁热打铁巩固一下自己的学习成果吧!

[链接http://lx.lanqiao.cn/problem.page?gpid=T2850]