什么是并查集
顾名思义，并查集有两个最主要的作用：合并集合和查询某两个元素是不是在同一个集合内。
或者说：
并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中。其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，只能用并查集来描述。 ——百度百科
怎么实现并查集
思路
如果两个元素在一个集合里，那么我们可以把这一个集合理解为一个家族，一个元素是另外元素的父亲，如果集合中出现更多元素，那么这个家族会更加庞大，但无论如何，都会有一个最远公共祖先（我瞎命名的，方便描述），由于集合本身具有无序性，所以说这个最大的祖先可以是集合中的任何一个元素，所有以这个元素为祖宗的数就是集合中的数，现在假设在集合 \(A\) 中有这样的祖先 \(a\) ，如果想要将集合 \(A\) 与集合 \(B\) 合并，那么设集合 \(B\) 中的最远公共祖先为 \(b\) ，如果将 \(a\) 的祖先改成 \(b\) ，那么集合 \(A\) 、 \(B\) 中所有的元素都有一个共同的祖先，所以此时他们就被合并为同一个集合了。
这样子的话，如果想要查找 \(a\) 和 \(b\) 是否在一个集合中，只需要看他们的祖先是否相同了
ps:
有没有发现这样的思路与树很像？所以说并查集也是一种树形的数据结构，合并就是将森林变成树，而查询则是查询两个子节点是否在同一棵树上
实现
模版题：洛谷P3367
首先是一个必不可少的数组： \(fa_i\) 即一个元素的父亲（稍后会有优化），一开始，每个元素自己为一个集合，所以说初始化，令元素的父亲为自己：
for(int i=1;i<=n;i++){
fa[i]=i;
}
接下来，如何寻找祖宗呢？这里采用递归的方式，如果一个元素的父亲是它本身的话，那么他就是这个集合中的最远公共祖先，所以可以写出 \(find()\) ：
int find(int x){
if(fa[x]==x) return x;
return find(fa[x]);
}
合并集合也就是让一个集合的祖宗的父亲为另一个集合的祖宗：
fa[find(y)]=find(z);
查询操作：
if(find(y)==find(z))
完整代码：
#include<stdio.h>
int fa[10005];
int find(int x){
if(fa[x]==x) return x;
return find(fa[x]);
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
fa[i]=i;
}
for(int i=1;i<=m;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
if(x==1){
fa[find(y)]=find(z);
}
else{
if(find(y)==find(z)){
printf("Y\n");
}
else{
printf("N\n");
}
}
}
return 0;
}
这时候我们会发现一个很尴尬的问题——超时了。
优化
考虑 \(fa_i\) 可以直接保存它的祖先而非父亲，这样递归函数可以省去很多时间，也就是说，我们可以将原来的树转化为一个除了根节点就是叶子的树，于是修改 \(find()\) ：
int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
得到 \(ACcode\) ：
#include<stdio.h>
int fa[10005];
int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
fa[i]=i;
}
for(int i=1;i<=m;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
if(x==1){
fa[find(y)]=find(z);
}
else{
if(find(y)==find(z)){
printf("Y\n");
}
else{
printf("N\n");
}
}
}
return 0;
}
并查集的应用
直接套用：
洛谷P1536
这题太过于板了，不给过程了。
最小生成树——— \(Kruskal\) 算法
什么是最小生成树
一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。 ——百度百科
或者说，在有 \(n\) 个节点的有 \(k\) 条边的图里保留 \(n-1\) 条边，使边的长度总和最小
什么是 \(Kruskal\)
一种用来实现最小生成树的算法
其原理类似贪心，从小到大地顺次排列 \(k\) 条边，在不出现自环的情况下顺次加入边，直至加入 \(n-1\) 条边
\(Kruskal\) 与并查集的联系
并查集起到的作用是：查自环
如果两个点已经属于一个集合（联通）时，那么再出现一条链接两点的边，必定形成自环。
代码
#include<stdio.h>
#include<algorithm>
using namespace std;
int n,m;
int fa[5005];
int ans,cnt;
struct e{
int x,y,c;
}edge[200005];
bool cmp(e a,e b){
return a.c<b.c;
}
int find(int x){
if(fa[x]==x) return fa[x];
else return fa[x]=find(fa[x]);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].c);
}
sort(edge+1,edge+1+m,cmp);
for(int i=1;i<=n;i++){
fa[i]=i;
}
for(int i=1;i<=m;i++){
int k=find(edge[i].x);
int p=find(edge[i].y);
if(k==p){
if(i==m){
printf("orz");
return 0;//无法实现
}
}
else{//查自环
fa[k]=p;
ans+=edge[i].c;
cnt++;
if(cnt==n-1){
break;
}
}
}
printf("%d",ans);
return 0;
}
技巧——反集
例题：洛谷P1892
如果 \(a\) 不在 \(A\) 集合中，那么我们可以理解为它在‘不在 \(A\) 集合’的集合中，那此时，我们可以把不在 \(A\) 集合中的元素全部都放到这个集合里去，我们可以理解为：这个集合就是 \(A\) 的反集。
在这道题中，如果 \(a\) 与 \(b\) 是敌人，那么我们把 \(a+n\) 与 \(b\) 合并，这就相当于将 \(b\) 加入与 \(a\) 为友的反集，这样子所有在反集里的元素都是朋友，也都是 \(a\) 的敌人，满足敌人的敌人是朋友的题意。
同理，如果 \(a\) 是 \(b\) 的朋友，那么将 \(a\) 与 \(b\) 合并，此时所有 \(b\) 的朋友也成为了 \(a\) 的朋友，这符合朋友的朋友是朋友的题意
所以代码如下：
#include<stdio.h>
#include<iostream>
using namespace std;
int n,m;
int fa[2005];
int find(int x){
if(fa[x]==x) return fa[x];
else return fa[x]=find(fa[x]);
}
int ans;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=2*n;i++){
fa[i]=i;
}
for(int i=1;i<=m;i++){
char a;
int b,c;
cin>>a;
scanf("%d%d",&b,&c);
if(a=='E'){
fa[find(b+n)]=find(c);
fa[find(c+n)]=find(b);
}
if(a=='F'){
fa[find(b)]=fa[find(c)];
}
}
for(int i=1;i<=n;i++){
if(fa[i]==i)ans++;
}
printf("%d",ans);
return 0;
}
结语
本文只讲述了很基础的有关于并查集的知识，作者也需要再学习，有任何不当请批评指正，谢谢。
标签：元素,return,int,查集,笔记,学习,fa,集合,find From： https://www.cnblogs.com/nxhx/p/disjoint-set_basic.html