首页 > 代码库 > 喵哈哈村的代码传说 第四章 并查集
喵哈哈村的代码传说 第四章 并查集
描述
有一个非常大的村子，叫做喵哈哈村，一开始他们都互相不认识，但是渐渐地，他们就会相互来往，所以就会有以下问题的产生：
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
自己写的丑代码，一直TLE
#include<iostream> #include<cstring> #include<cstdio> using namespace std; int a[100006]; int find(int x,int y) { int t; while(a[x]) { t=a[x]; if(t==y){return 1;} x=t; } return 0; } int main() { int n,x,y,b,m; while(scanf("%d%d",&n,&m)) { memset(a,0,sizeof(a)); while(m--) { scanf("%d%d%d",&b,&x,&y); if(b==1) a[x]=y; else { if(x==y) cout<<"Yes"<<endl; else {int c=find(x,y); if(c) cout<<"Yes"<<endl; else cout<<"No"<<endl; } } } } return 0; }
大佬的递归代码
#include<iostream> #include<cstring> using namespace std; int a[100005]; int find(int x) { return a[x]==x?x:a[x]=find(a[x]); } void search(int x,int y) { x=find(x); y=find(y); a[x]=y; } int main() { int n,m; while(cin>>n>>m) { for(int i=1;i<=n;i++) { a[i]=i; } while(m--) { int k,b,c; cin>>k>>b>>c; if(k==1) { search(b,c); } else{ if(find(b)==find(c)) cout<<"Yes"<<endl; else cout<<"No"<<endl; } } } return 0; }
喵哈哈村的代码传说 第四章 并查集
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。