并查集
在近乎O（1）的时间完成下面的操作
将两个集合合并
询问两个集合是否在同一个集合中
一、板子题********************
1、思路
用树来存储每一个集合，根节点的编号就是那个集合的编号，每个节点存储它的父节点，p[x]表示x的父节点
(1)如何判断是不是根节点？
只有根节点是p[x]==x的，其余都不是
(2)如何求x的集合编号？
while(p[x]!=x) x=p[x] 只要不是树根，就继续往上找
经过路径压缩的优化后，在找其中一个数的根节点时，将路上所有的节点都指向根节点。
(3)如何合并两个集合？
把其中一个集合直接接到令一个集合的根节点下
px是集合x的集合编号，py是集合y的集合编号，令p[x]=y就行
2、代码模板
#include<iostream>
using namespace std;
const int N=1e5+10;
int n,m;
int p[N]; //存的每个数的父节点是谁，初始的时候每个元素都是一个集合
int find(int x) //找到x的根节点+路径压缩
{
if(p[x]!=x) //如果此时没找到根节点
p[x]=find(p[x]); //递归继续找
return p[x]; //找到了就返回根节点
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
p[i]=i; //刚开始每个元素的父节点都是自己
while(m--)
{
char op[2];
int a,b;
scanf("%s%d%d",op,&a,&b);
if(op[0]=='M') //合并操作
p[find(a)]=find(b); //把a集合并到b下面
else //查找操作
{
if(find(a)==find(b))
puts("Yes");
else
pus("No");
}
}
return 0;
}
二、并查集+统计集合个数************************
1、思路
多了个统计集合元素个数
2、代码模板
#include<iostream>
using namespace std;
const int N=1e5+10;
int n,m;
int p[N],size[N]; //size[N]记录每个集合的大小
int find(int x) //找到x的根节点+路径压缩
{
if(p[x]!=x) //如果此时没找到根节点
p[x]=find(p[x]); //递归继续找
return p[x]; //找到了就返回根节点
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
p[i]=i; //刚开始每个元素的父节点都是自己
size[i]=1; //最开始元素总和都是1
}
while(m--)
{
char op[2];
int a,b;
scanf("%s",op);
if(op[0]=='C') //合并操作
{
scanf("%d%d",&a,&b);
if(find(a)==find(b))
continue;
size[find(b)]+=size[find(a)];
p[find(a)]=find(b); //把a集合并到b下面
}
else if(op[1]=='1') //查找操作
{
scanf("%d%d",&a,&b);
if(find(a)==find(b))
puts("Yes");
else
pus("No");
}
else
{
scanf("%d",&a);
printf("%d\n",size[find(a)]);
}
}
return 0;
}
三、并查集判环问题
1、思路
对于每一个点，我们依次将它们划分集合，如果2个点已经在同一个集合中，即存的集合元素相等，这次合并就会构成一个环。
这道题的话，还需要将二维坐标转化为一维的。当x,y都是依次递增时，可以通过x*n+y来实现。
2、代码
#include<iostream>
using namespace std;
const int N=4e4+10;
int p[N];
int n,m;
int get(int x,int y)//这里是将二维坐标转化为一维不重复数字,方便并查集合并
{
return x*n+y; //当x和y中没有重复元素时,且从0开始时,常用的就是x*n+y
}
int find(int x)//并查集操作
{
if(x!=p[x])
p[x]=find(p[x]);
return p[x];
}
int main()
{
//cin读入的好处是可以过滤掉空、格回、车制表符
cin.tie(0);
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=0;i<n*n;i++)//初始化
p[i]=i;
int res=0;
for(int i=1;i<=m;i++)//读入边
{
int x,y;
char ch;
cin>>x>>y>>ch;
x--,y--;
int a,b;
a=get(x,y);
if(ch=='D')//往下走
b=get(x+1,y);
else //往右走
b=get(x,y+1);
int pa=find(a),pb=find(b);//分别寻找属于哪个集合
if(pa==pb)//如果2点再同一个集合中,那么这次合并后就会出现环
{
res=i; //记录答案
break;
}
p[pa]=pb; //如果不在一个集合中,合并
}
if(!res)
cout<<"draw";
else
cout<<res;
return 0;
}
四、并查集+路径压缩+集合大小**********************
1、思路
在并查集合并的时候，我们用size数组记录下每个集合的元素个数大小，d数组记录到这个点到自己集合的根节点的距离。这道题也比较特殊，没有分支情况（集合大小就是最下面的点到根节点的距离），在集合合并时(假设是a合并到b下面)，我们也需要额外将d[pa]+=size[pb]，即让a集合的根节点加上b的集合大小。sz[pb]+=sz[pa]让b集合的大小加上a集合的。
2、代码
#include<iostream>
using namespace std;
const int N=3e4+10;
int n,p[N],sz[N],d[N];// p是并查集,sz是当前下标所在集合大小,d是到根节点的距离
int find(int x) //并查集+路径压缩
{
if(x!=p[x])
{
int root=find(p[x]); //记录下当前根节点
d[x]+=d[p[x]]; //当前点到根节点的距离加上根节点到它的根节点的距离(路径压缩)
p[x]=root;
}
return p[x];
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=N;i++)//初始化并查集和大小
{
p[i]=i;
sz[i]=1; //初始每个集合的大小为1
}
while(n--)
{
char op[2];
int a,b;
scanf("%s %d %d",op,&a,&b);
int pa=find(a),pb=find(b);
if(op[0]=='M')//合并操作
{
if(pa!=pb) //不在同一个集合中
{
p[pa]=pb; //将a并到b集合后面
d[pa]=sz[pb]; //a集合到根节点的距离,就是b集合的长度
sz[pb]+=sz[pa]; //b集合的长度，加上a集合的长度
}
}
else //询问操作
{
if(pa!=pb)
puts("-1");
else
printf("%d\n",max(0,abs(d[a]-d[b])-1));
}
}
return 0;
}
5、边带权并查集
1、思路
2、代码模板
投递摩尔线程等公司10个岗位