http://poj.org/problem?id=1308
1 #include<stdio.h> 2 #include<string.h> 3 #define N 100001 4 int bin[N],flag; 5 int find(int x) 6 { 7 //不压缩路径 8 /*int r=x; 9 while(bin[r]!=r) 10 r=bin[r]; 11 return r;*/ 12 13 //压缩路径 14 int k,t; 15 t=x; 16 while(t!=bin[t]) 17 t=bin[t]; 18 while(x!=t) //修改路径---压缩 19 { 20 k=bin[x]; 21 bin[x]=t; 22 x=k; 23 } 24 return x; 25 } 26 void merge(int x,int y) 27 { 28 int fx,fy; 29 fx=find(x); 30 fy=find(y); 31 if(fx==fy) 32 flag=1; 33 else 34 bin[fx]=fy; 35 } 36 int main() 37 { 38 int a,b,i,min,max,h[N],l=1; 39 while(scanf("%d%d",&a,&b)) 40 { 41 if(a==-1&&b==-1)break; 42 flag=-1; 43 memset(h,-1,sizeof(h)); 44 if(a==0&&b==0) 45 { 46 printf("Case %d is a tree.\n",l++); 47 continue; 48 } 49 else if(a==b) 50 flag=1; 51 max=a>b?a:b; 52 min=a<b?a:b; 53 if(max<(a>b?a:b)) 54 max=a>b?a:b; 55 if(min>(a<b?a:b)) 56 min=a<b?a:b; 57 for(i=0;i<N;i++) 58 bin[i]=i; 59 bin[a]=b; 60 h[a]=h[b]=1; 61 while(scanf("%d%d",&a,&b)) 62 { 63 if(a==0&&b==0)break; 64 h[a]=h[b]=1; 65 if(flag==1)continue; 66 if(max<(a>b?a:b)) 67 max=a>b?a:b; 68 if(min>(a<b?a:b)) 69 min=a<b?a:b; 70 merge(a,b); 71 } 72 if(flag==1) 73 printf("Case %d is not a tree.\n",l++); 74 else{ 75 for(i=min;i<=max;i++) 76 { 77 if(bin[i]==i&&h[i]==1) 78 flag++; 79 } 80 if(flag==0) 81 printf("Case %d is a tree.\n",l++); 82 else 83 printf("Case %d is not a tree.\n",l++); 84 } 85 } 86 return 0; 87 }