#include<cstdio>
const int maxn=5005;
int p[maxn];
int find(int x){
return (p[x]==x?x:p[x]=find(p[x]));
}
int main(){
// freopen("P1034.in","r",stdin);
int n,m,q,a,b;
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++) p[i]=i;
for(int i=1;i<=m;i++){
scanf("%d%d",&a,&b);
int x=find(a);
int y=find(b);
if(x!=y) p[x]=y;
}
for(int i=1;i<=n;i++) p[i]=find(i);
for(int i=1;i<=q;i++){
scanf("%d%d",&a,&b);
if(p[a]==p[b]) printf("Yes\n");
else printf("No\n");
}
return 0;
}
过了QAQ
2 条评论
-
Fan_T LV 7 @ 2016-09-26 13:56:00
仰望高端玩家QAQ
-
@ 2016-09-23 22:23:44
#include<iostream> using namespace std; int n,m,p,f[5010]; int find(int x) { if(f[x]!=x) f[x]=find(f[x]); return f[x]; } void putin() { cin>>n>>m>>p; int a,b; for(int i=1;i<=n;i++) f[i]=i; for(int i=1;i<=m;i++){ cin>>a>>b; if(a<b) f[find(a)]=find(b); else f[find(b)]=find(a); } } void work() { int a,b; for(int i=1;i<=p;i++) { cin>>a>>b; if(f[a]==f[b]) cout<<"Yes\n"; else cout<<"No\n"; } } int main() { putin(); for(int i=1;i<=n;i++) f[i]=find(f[i]); work(); return 0; }蒻苟的并查集
-
@ 2016-11-27 05:05:46
没必要比较a,b的大小的
-
- 1
