#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int n,m,p,x,y,xymin,xymax;
cin>>n>>m>>p;
int a[5001];
for(int i=0; i<=5000; i++) a[i]=0;
int k=1;
for(int i=1; i<=m; i++)
{
cin>>x>>y;
if(!a[x]&&!a[y])
{
a[x]=a[y]=k;
k++;
}
else if(!a[x]&&a[y])
a[x]=a[y];
else if(a[x]&&!a[y])
a[y]=a[x];
else if(a[x]&&a[y])
{
xymin=min(a[x],a[y]);
xymax=max(a[x],a[y]);
for(int j=1; j<=n; j++)
if(a[j]==xymax)
a[j]=xymin;
}
}
for(int i=1;i<=p;i++)
{
cin>>x>>y;
if(a[x]==a[y])
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
return 0;
}
3 条评论
-
Anilop LV 8 @ 2016-06-12 18:50:51
我也只过了一个点
-
@ 2016-06-12 13:24:07
#include <iostream> #include <cstring> #include <cstdio> using namespace std; int n,m,s,t[5001]={0},pre[5001]; int find(int x) { int r=x; while (pre[r]!=r) r=pre[r]; return r; } int main() { int i,j,k,x,y; scanf("%d%d%d",&n,&m,&s); for (i=1;i<=n;i++) pre[i]=i; for (i=0;i<m;i++) { scanf("%d%d",&x,&y); int fx=find(x),fy=find(y); if (fx!= fy) pre[fx]=fy; } for (i=0;i<s;i++) { scanf("%d%d",&x,&y); if(find(x)==find(y)) t[i]=1; } for (i=0;i<s;i++) if (t[i]==1) printf("Yes\n"); else printf("No\n"); }为什么不用并查集呢？
-
@ 2016-06-12 13:24:02
#include <iostream> #include <cstring> #include <cstdio> using namespace std; int n,m,s,t[5001]={0},pre[5001]; int find(int x) { int r=x; while (pre[r]!=r) r=pre[r]; return r; } int main() { int i,j,k,x,y; scanf("%d%d%d",&n,&m,&s); for (i=1;i<=n;i++) pre[i]=i; for (i=0;i<m;i++) { scanf("%d%d",&x,&y); int fx=find(x),fy=find(y); if (fx!= fy) pre[fx]=fy; } for (i=0;i<s;i++) { scanf("%d%d",&x,&y); if(find(x)==find(y)) t[i]=1; } for (i=0;i<s;i++) if (t[i]==1) printf("Yes\n"); else printf("No\n"); }为什么不用并查集呢？
- 1
