6 8 5 3 5 2 6 4 5 6 0 0 8 1 7 3 6 2 8 9 7 5 7 4 7 8 7 6 0 0 3 8 6 8 6 4 5 3 5 6 5 2 0 0 -1 -1
Yes Yes No
include<stdio.h> int set[100050]; int v[100050]; int find(int p) { int t; int child=p; while(p!=set[p])//查找根节点 p=set[p]; while(child!=p) { t=set[child]; set[child]=p; child=t; } return p; } int merge(int x,int y)//合并 { int fx=find(x); int fy=find(y); if(fx!=fy) { set[fx]=fy; return 1; } else return 0; } int main() { int a,b; int i; while(scanf("%d%d",&a,&b)!=EOF&&a!=-1&&b!=-1) { int w=1; if(a==0&&b==0)//这是个大坑!!!! { printf("Yes\n"); continue; } for(i=0;i<=100050;i++) { set[i]=i; v[i]=0;//标记是否被访问过 } int min=9999999,max=-1; while(a||b)//寻找出所出现 的最大值和最小值 { if(a>max) max=a; if(b>max) max=b; if(a<min) min=a; if(b<min) min=b; v[a]=1; v[b]=1;//标记为1 if(!merge(a,b))//判断 是否为环,即是否符合题意 w=0; scanf("%d%d",&a,&b); } int count=0; if(w==0) printf("No\n"); else { for(i=min;i<=max;i++)//找出树的个数 { if(v[i]&&set[i]==i) count++; } if(count==1) printf("Yes\n"); else printf("No\n"); } } return 0; }
版权声明:本文为博主原创文章,未经博主允许不得转载。
原文:http://blog.csdn.net/zhangxiaoxiang123/article/details/47425903