概述
正如百度百科所说，并查集是一种树形的数据结构，并且用于处理一些不相交集合的合并及查询问题。一般地来说，并查集由两个部分组成，一个是查找要操作的两个集合是否属于同一个，另一个则是进行这两个集合合并的过程。
并查集中，每一个集合用一个标识来表示，一般来说，大家都会选择这棵树的根作为这个标识。我们根据每棵树的标记来判断某些节点是否在同一个集合中，也就是是否属于同一棵树。
正文
就我目前的理解来说，并查集本身其实只包含三个部分：初始化，查找与合并。而其中查找与合并两个部分，有可能边并边查，也同样有可能先并再查，这都无可厚非，并且不影响并查集本身的工作。在查找和合并这两个步骤又分别包含了两种优化方式，也就是我们常说的路径压缩和按秩合并。
并查集本身
初始化
并查集是一种树形的数据结构。我们要运用并查集求解问题，就需要构建树。我们首先把每个节点的标记初始化为它自身，也就是说每个节点自成一棵树，这个节点既是自己的父亲（f数组记录），也是自己的祖宗（find函数查找）。
用代码实现就是如下效果
for(int i=1;i<=n;i++) //n为节点数
{
f[i]=i; //f数组记录节点的父节点
}
查找
我们可能需要对某两个节点进行判断，判断他们之间是否存在某种关系（比如是否是敌人或者是否是朋友）。此时我们只需找到两个节点的祖先（find函数返回的值）并且判断两个节点的祖先是否相等。
这里就出现了一个问题，我们每次寻找祖先的时候都需要不断上访节点的父亲，假如某个辈分极低的节点被反复查询，该极长的路径被反复遍历。抑或是该辈分极低的节点被查询过，而在它上面的节点又被查询，就会导致某一条路被反复遍历，无疑浪费了时间。这里就引出了第一种优化方式：路径压缩。当然我们在此只是提一句，下面并查集优化的时候再详细讲解。
这里的查找函数写法有两种，一种是递归写法，一种是非递归写法，我都写在下面，仅供参考。
这里是递归写法：
int find(int r)
{
if(f[r]==r)
{
return r;
}
else
{
return find(f[r]);
}
}
这里是非递归写法：
int find(int r)
{
while(f[r]==r)
{
r=f[r];
}
return r;
}
合并
并查集的过程中，既需要查找，也需要合并。当两个节点当前所处集合不同，但实际上应该处于同一集合时，我们需要将这两个集合合并。当然，我们并不能只是合并这两个点，而是应该查找它们的祖先节点，并且合并两个祖先节点，选择一个祖先节点为两个集合共同的祖先节点（也即代表节点）。
我们只需要把其中一个祖先节点的父亲节点赋值成另外一个祖先节点即可完成该操作。
if(find(a)!=find(b))
{
f[find(a)]=find(b);
}
这里可以提前把a节点和b节点的祖先赋给两个变量来缩减代码量。
在这里，又可以引出另一个优化的可能，那就是在合并的时候，可能会出现一大一小两棵树（也可以称作一大一小两个集合），若把大树并到了小树上，就会导致最长的路径越来越长以致于查询的时候需要遍历的节点不断增多。由此引出了按秩合并的思路，我们总寻找小树，并且把小树并到大树上。这里也暂作引出，下面来解释优化操作。
并查集优化
我们很明显可以看出来，并查集本身的时间消耗还是比较大的，并且存在着大量的重复遍历操作，下面我来解释两种常见的优化方式。单独用按秩合并可以将并查集的时间复杂度降低到O(nlogn)，既n乘以2为底n的对数，单独使用路径压缩则会提升查找效率。而两种一起用甚至可以将每一步查找、合并的时间复杂度降低至O(α(n))，其中α(n)名为反阿克曼函数。阿克曼函数极剧增长而反阿克曼函数几乎不增长，我们可以将优化后的并查集时间复杂度看作O(n)，n为操作数。
至于为什么会被优化这么多，以至于达到了O(n)的线性增长关系，相信我解释完这两种优化方式之后你心中会有一点答案。
路径压缩
首先，路径压缩，正如我上面查找步骤讲解中所说，在某一条极长路径中，一些路径会被反复遍历，从而造成重复冗余。所以，我们在查找的时候，对于每一个节点，改变它们的路径，让他们直接连接在根节点（标识节点）也即祖先节点下，使他们与祖先节点成为父子关系。这样，在再次查询这些点的时候，仅需最多两次查找即可查询到它们的祖先节点。
int find(int r)
{
if(f[r]==r)
{
return r;
}
else
{
return f[r]=find(f[r]);
}
}
这是一种递归形式，在递归的过程中就把祖先节点赋值成了这些过程中包含的节点的父亲。
按秩合并
然后，按秩合并，也正如我上面合并步骤讲解中所说，大树合并到小树上的时候会造成不小的麻烦，所以我们在合并之前判断一下两个集合的大小关系，并且把小树合并到大树上。我们将这个大小关系规定成口中的“秩”。这个“秩”既可以代表树的高度，也可以代表集合内节点的数量。但是在这里要注意了！！！只有在没有使用路径压缩的时候才可以用“秩”代表树的高度，因为一旦路径压缩，所有的子节点全部与祖先节点直连，树的高度都将被划成2。故一般在同时使用两种优化方式时，通常直接把秩看作了节点数量。
int azhb(int l,int r)
{
if(jds[find(l)]<jds[find(r)])
{
f[find(l)]=find(r);
jds[find(r)]+=jds[find(l)];
}
else
{
f[find(r)]=find(l);
jds[find(l)]+=jds[find(r)];
}
}
在这里，我规定传进来的参数为两个原始节点，然而这样会比较麻烦，所以我一般在用到按秩合并的时候都会直接将两个祖先节点传进来，以便于直接使用jds（节点数）这个数组。ps：函数名就是按秩合并的缩写，不要吐槽这个……
时间复杂度分析
我们降低问题的复杂程度，假设只需要进行n次操作，所有的查找都在合并操作之后出现。对于每个需要访问的节点x，在其第一次被查找的时候就会被路径压缩优化成与祖先节点直连，当再次访问x节点的时候，只需要最多两次最少一次的访问。而按秩合并则会一直保证不会出现高度大于2的树出现。两种优化方式一起出现，会直接将并查集的时间复杂度降低到线性增长关系。
其中反阿克曼函数有关的知识，有兴趣的话可以自行查找理解学习，我暂时没太大兴趣，也许之后会深入学习一下。
引例讲解全过程
来看这个例子，实际上这个输入输出样例是洛谷P3367 并查集的一道模板题，我把它拿下来当作例子来讲解一下。
首先看输入，4个点，7个操作。每个操作的第一个数字，1代表着合并操作，2代表着查询操作。
一开始对这四个点进行初始化：
这四个点，每一个都是独立的一个集合。
然后我们开始进行操作，第一条操作查找，我们就直接用find函数寻找祖先，发现都是它们本身，判断出来不在同一集合，肯定输出N。
第二条操作和第四条操作分别合并1 2以及3 4，合并之后的效果就是这样。
而在此时，操作要求把2和3合并，我们查询2的祖先发现是1，查询3的祖先，发现就是3本身，故合并1与3。
如果加入了路径压缩，在下一次操作也就是最后一次操作的时候，需要查询1和4，此时会在查询的过程中，将4直连到1的下面。
而由于这个例子不算复杂，体现不出来按秩合并以及路径压缩的真意。我来稍微让这个例子变得复杂一些，再分析一下。
我们在4节点的下面再连接一个5节点
如果我们不考虑按秩合并，只进行路径压缩，把3节点并到1上面。
这样我们在下次查询5的时候，进行路径压缩，需要转移4和5两次。这样看来，把1并给3的时候也会转移两次，好像没什么太大的时间优势。但是当长链够长的时候，按秩合并的时间优势就会体现出来，并且把时间复杂度大幅优化。
在我出的这个例子中，貌似把“秩”当作树的高度也可以，但是试想一下经过路径压缩之后，每个集合都变成了一个根节点下面连着数个节点的多叉树，所以路径压缩之后的并查集，“秩”还是当作节点数好一些。
下面我来贴出我模板的代码
#include<stdio.h>
int f[10005];
int jds[10005]={0};
int find(int r)
{
if(f[r]==r)
{
return r;
}
else
{
return f[r]=find(f[r]);
}
}
int azhb(int l,int r)
{
if(jds[l]<jds[r])
{
f[l]=r;
jds[r]+=jds[l];
}
else
{
f[r]=l;
jds[l]+=jds[r];
}
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
int a,b,c;
int fb,fc;
for(int i=1;i<=n;i++)
{
f[i]=i;
}
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
fb=find(b);
fc=find(c);
if(a==1)
{
if(fb!=fc)
{
azhb(fb,fc);
}
}
else
{
if(fb==fc)
{
printf("Y\n");
}
else
{
printf("N\n");
}
}
}
return 0;
}
别吐槽我的变量名和函数名＞﹏＜
多关系并查集
例题
洛谷 P1551 亲戚
题目
https://www.luogu.org/problem/P1551
思路
就是一个裸的并查集。
代码
#include<stdio.h>
int f[10005];
int jds[10005];
int a,b;
int fa,fb;
int find(int r)
{
if(f[r]==r)
{
return r;
}
else
{
return f[r]=find(f[r]);
}
}
int azhb(int l,int r)
{
if(jds[l]<jds[r])
{
f[fa]=fb;
jds[r]+=jds[l];
}
else
{
f[fb]=fa;
jds[l]+=jds[r];
}
}
int main()
{
int n,m,p;
scanf("%d%d%d",&n,&m,&p);
for(int i=1;i<=n;i++)
{
f[i]=i;
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
fa=find(a);
fb=find(b);
if(fa!=fb)
{
azhb(fa,fb);
}
}
for(int i=1;i<=p;i++)
{
scanf("%d%d",&a,&b);
if(find(a)==find(b))
{
printf("Yes\n");
}
else
{
printf("No\n");
}
}
return 0;
}
洛谷 P2820 局域网
题目
https://www.luogu.org/problem/P2820
思路
这是一个最小生成树的题目，几乎可以算是裸的最小生成树，有关最小生成树的算法在之后我会开专题讲解。这里我来简单阐述一下这道题我用到的，我这道题用到了克鲁斯卡尔，大概思路就是，先把图中所有路径从小到大排序，然后逐个进行判断，若两个点不在同一集合则合并，若在同一集合则往下过，直到图中所有点都已经进入点集。
简单来说，就是一种排序算法先对数据进行处理，然后再用并查集最后求得最小值。
代码
#include<stdio.h>
int v[10005]={0};
int f[10005];
int jds[10005];
struct a
{
int begin;
int end;
int w;
}a[10005];
int find(int r)
{
if(f[r]==r)
{
return r;
}
else
{
return f[r]=find(f[r]);
}
}
int azhb(int l,int r)
{
if(jds[l]<jds[r])
{
f[l]=r;
jds[r]+=jds[l];
}
else
{
f[r]=l;
jds[l]+=jds[r];
}
}
int main()
{
int n,k;
int t;
int fa,fb;
int sum=0;
scanf("%d%d",&n,&k);
for(int i=1;i<=k;i++)
{
scanf("%d%d%d",&a[i].begin,&a[i].end,&a[i].w);
}
for(int i=1;i<=k;i++)
{
f[i]=i;
jds[i]=1;
}
for(int i=k;i>=1;i--)
{
for(int j=1;j<=i-1;j++)
{
if(a[j].w>a[j+1].w)
{
t=a[j].w;
a[j].w=a[j+1].w;
a[j+1].w=t;
t=a[j].begin;
a[j].begin=a[j+1].begin;
a[j+1].begin=t;
t=a[j].end;
a[j].end=a[j+1].end;
a[j+1].end=t;
}
}
}
for(int i=1;i<=k;i++)
{
fa=find(a[i].begin);
fb=find(a[i].end);
if(fa!=fb)
{
azhb(fa,fb);
v[i]=1;
}
}
for(int i=1;i<=k;i++)
{
if(v[i]==0)
{
sum+=a[i].w;
}
}
printf("%d",sum);
return 0;
}
洛谷 P3144 [USACO16OPEN]关闭农场Closing the Farm_Silver
题目
https://www.luogu.org/problem/P3144
思路
这个题可以倒着想，逐渐加边进去。因为并查集只能合并以及查询，也就是不断加边进图，而不能从图中删除边，所以很自然的想到倒着加边进去然后判断一共有几个集合，时间复杂度也不会很高。
代码
#include<stdio.h>
int dian[3005]={0};
int sc[3005];
int f[3005];
int v[3005][3005]={0};
int jl[3005];
int jds[3005];
int jhs;
int a,b;
int find(int r)
{
if(f[r]==r)
{
return r;
}
else
{
return f[r]=find(f[r]);
}
}
int azhb(int l,int r)
{
if(jds[l]<jds[r])
{
f[l]=r;
jds[r]+=jds[l];
}
else
{
f[r]=l;
jds[l]+=jds[r];
}
}
int main()
{
int n,m;
jhs=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
v[a][b]=1;
v[b][a]=1;
}
for(int i=1;i<=n;i++)
{
f[i]=i;
}
for(int i=n;i>=1;i--)
{
scanf("%d",&jl[i]);
}
sc[1]=1;
dian[jl[1]]=1;
for(int i=1;i<=n;i++)
{
if(v[jl[1]][i]==1)
{
if(dian[i]==1)
{
azhb(find(jl[1]),find(i));
}
}
}
for(int i=2;i<=n;i++)
{
jhs=0;
for(int j=1;j<=n;j++)
{
if(v[jl[i]][j]==1)
{
if(dian[j]==1)
{
azhb(find(jl[i]),find(j));
}
}
}
dian[jl[i]]=1;
for(int j=1;j<=n;j++)
{
if(dian[j]==1&&f[j]==j)
{
jhs++;
}
}
if(jhs>1)
{
sc[i]=0;
}
else
{
sc[i]=1;
}
}
for(int i=n;i>=1;i--)
{
if(sc[i]==1)
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}
return 0;
}
洛谷 P3958 奶酪
题目
https://www.luogu.org/problem/P3958
思路
这道题我把奶酪的上表面空气与下表面空气看作了两个横跨长宽的大集合，然后当有可以通向下面的奶酪洞存在时，我便将下表面空气的大集合和该奶酪洞合并，上表面空气也是一样的操作，最后查询上表面空气和下表面空气是否存在于一个集合中即可完成。
代码
#include<stdio.h>
#include<math.h>
int f[10005];
int jds[10005];
int n,h,r;
struct a
{
long long x;
long long y;
long long z;
}a[1005];
int find(int r)
{
if(f[r]==r)
{
return r;
}
else
{
return f[r]=find(f[r]);
}
}
long long pf(long long q)
{
return q*q;
}
void azhb(int l,int r)
{
if(jds[l]<jds[r])
{
f[l]=r;
jds[r]+=jds[l];
}
else
{
f[r]=l;
jds[l]+=jds[r];
}
}
int main()
{
int t;
scanf("%d",&t);
for(int i=1;i<=t;i++)
{
scanf("%d%d%d",&n,&h,&r);
for(int j=1;j<=n;j++)
{
f[j]=j;
jds[j]=0;
}
f[2000]=2000;
jds[2000]=0;
f[3000]=3000;
jds[3000]=0;
for(int j=1;j<=n;j++)
{
scanf("%lld%lld%lld",&a[j].x,&a[j].y,&a[j].z);
}
for(int j=1;j<=n;j++)
{
for(int k=1;k<=n;k++)
{
if(sqrt(pf(a[j].x-a[k].x)+pf(a[j].y-a[k].y)+pf(a[j].z-a[k].z))<=(r*2))
{
azhb(find(j),find(k));
}
}
if((a[j].z)<=r)
{
azhb(find(j),find(2000));
}
if((a[j].z)>=h-r)
{
azhb(find(j),find(3000));
}
}
if(find(2000)==find(3000))
{
printf("Yes\n");
}
else
{
printf("No\n");
}
}
return 0;
}
洛谷 P2078 朋友
题目
https://www.luogu.org/problem/P2078
思路
这道题就是两个并查集。
代码
#include<stdio.h>
#include<math.h>
int f1[10005];
int f2[10005];
int jds1[10005];
int jds2[10005];
int jdz(int r)
{
if(r<0)
{
return -r;
}
else
{
return r;
}
}
int min(int l,int r)
{
if(l<r)
{
return l;
}
else
{
return r;
}
}
int find1(int r)
{
if(f1[r]==r)
{
return r;
}
else
{
return f1[r]=find1(f1[r]);
}
}
int azhb1(int l,int r)
{
if(jds1[l]<jds1[r])
{
f1[l]=r;
jds1[r]+=jds1[l];
}
else
{
f1[r]=l;
jds1[l]+=jds1[r];
}
}
int find2(int r)
{
if(f2[r]==r)
{
return r;
}
else
{
return f2[r]=find2(f2[r]);
}
}
int azhb2(int l,int r)
{
if(jds2[l]<jds2[r])
{
f2[l]=r;
jds2[r]+=jds2[l];
}
else
{
f2[r]=l;
jds2[l]+=jds2[r];
}
}
int main()
{
int n,m,p,q;
int fa,fb;
int a,b;
scanf("%d%d%d%d",&n,&m,&p,&q);
for(int i=1;i<=n;i++)
{
f1[i]=i;
jds1[i]=1;
}
for(int i=1;i<=m;i++)
{
f2[i]=i;
jds2[i]=1;
}
for(int i=1;i<=p;i++)
{
scanf("%d%d",&a,&b);
fa=find1(a);
fb=find1(b);
if(fa!=fb)
{
azhb1(fa,fb);
}
}
for(int i=1;i<=q;i++)
{
scanf("%d%d",&a,&b);
fa=find2(jdz(a));
fb=find2(jdz(b));
if(fa!=fb)
{
azhb2(fa,fb);
}
}
printf("%d",min(jds1[find1(1)],jds2[find2(1)]));
return 0;
}
未完待续…
Author: Maple
Link: http://www.unknown9t.com/2022/04/29/%E5%B9%B6%E6%9F%A5%E9%9B%86/
Copyright: All articles in this blog are licensed under CC BY-NC-SA 3.0 unless stating additionally.