首页 > 代码库 > 喵哈哈村的代码传说 第四章 并查集

喵哈哈村的代码传说 第四章 并查集

有一个非常大的村子,叫做喵哈哈村,一开始他们都互相不认识,但是渐渐地,他们就会相互来往,所以就会有以下问题的产生:

1 x y,x家与y家成为朋友

2 x y,提问x家和y家是否为朋友,间接成为朋友也算。

本题包含若干组测试数据。
第一行两个整数n,m,表示这个村子有n户家庭,一开始他们都不认识。含有m个问题。
接下来m行:
1 x y
2 x y
分别表示操作和询问。
满足1<=n,m<=100000,注意x

是朋友输出Yes,否则输出N

 

提交代码

#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,pre[100005],c;
int find(int x)
{
int r=x;
while ( pre[r] != r )
r=pre[r];

int i=x , j ;
while( i != r )
j = pre[ i ];
pre[ i ]= r ;
i=j;
}
return r ;
}
void join(int x,int y)
{
int fx=find(x),fy=find(y);
if(fx!=fy)
pre[fx]=fy;
}
int main()
{
while(scanf("%d%d",&n,&m)==2)
{
for(int i=1;i<=n;i++)
{
pre[i]=i;
}
for(int i=1;i<=m;i++)
{
cin>>c;
if(c==1){
cin>>x>>y;
join(x,y);
}
else{
cin>>x>>y;
if(find(x)==find(y)) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}

}
}

}

喵哈哈村的代码传说 第四章 并查集