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

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

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

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

 复制
3 4
2 1 2
2 1 1
1 1 2
2 1 2
No
Yes
Yes
这题比赛的时候没有做出来,比赛后看了大佬的代码才知道并查集这么好用,递归用的好神奇。
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 1e5+6;
 4 int n,m;
 5 int fa[maxn];
 6 int fi(int x){
 7     return fa[x]==x?x:fa[x]=fi(fa[x]);
 8 }
 9 void uni(int x,int y){
10     x = fi(x),y = fi(y);
11     fa[x]=y;
12 }
13 void solve(){
14     for(int i=1;i<=n;i++)fa[i]=i;
15     for(int i=0;i<m;i++){
16         int a,b,c;
17         scanf("%d%d%d",&a,&b,&c);
18         if(a==1){
19             uni(b,c);
20         }else{
21             if(fi(b)==fi(c)){
22                 cout<<"Yes"<<endl;
23             }else{
24                 cout<<"No"<<endl;
25             }
26         }
27     }
28 }
29 int main(){
30     while(cin>>n>>m)solve();
31     return 0;
32 }

 

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