2 条题解
-
2
兴科大厦蜀山区合肥市安徽省大中国地球太阳系银河系全宇宙最牛题解
#include using namespace std; const int maxn=5010; queue<int>q; int N,M,Q,fa[maxn],dep[maxn]; int Find(int x){//查询元素根节点 if(fa[x]==x)return x; return fa[x]=Find(fa[x]);//路径压缩操作,找到根节点后直接将元素x的父亲设为祖先。 } void Com(int x,int y){//合并元素x和元素y所在的集合 x=Find(x); y=Find(y); if(x==y)return; if(dep[x]>dep[y])fa[y]=x; else{ fa[x]=y; if(dep[x]==dep[y])dep[y]++; } } int main(){ ios::sync_with_stdio(false); int i,x,y; cin>>N>>M>>Q; for(i=1;i<=N;i++)fa[i]=i;//初始化 for(i=1;i<=M;i++){//对读入的亲戚关系进行合并 cin>>x>>y; Com(x,y); } for(i=1;i<=Q;i++){ cin>>x>>y; if(Find(x)==Find(y))q.push(1); else q.push(0); } while(!q.empty()){//判断两人是否为亲戚 if(q.front())puts("Yes"); else puts("No"); q.pop(); } return 0; }
未经允许,不得复制! 看后,给个赞 ❤️
-
2
世界上最好的题解:
#include<iostream> using namespace std; #define MAXN 5005 int f[MAXN]; int n,m,q; int find(int x){ if(f[x]==x)return x; else return f[x]=find(f[x]); } void join(int x,int y){ int f1=find(x),f2=find(y); if(f1!=f2){ f[f1]=f2; } } int main(){ cin>>n>>m>>q; for(int i=1;i<=n;++i)f[i]=i; int x,y; for(int i=1;i<=m;++i){ cin>>x>>y; join(x,y); } for(int i=1;i<=q;++i){ cin>>x>>y; if(find(x)==find(y))cout<<"Yes"; else cout<<"No"; cout<<endl; } return 0; }
请各位帮我点个赞呗!😄
- 1
信息
- ID
- 547
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 3
- 标签
- 递交数
- 16
- 已通过
- 12
- 上传者