判断是不是树
输入：
每输入一对都为0的数时，表示一组数据输入完毕。每条边有一对正整数表示，第一个数为有向边的起始边，第二个数为有向边的终止点。一对负数的输入就表示输入的结束。
输出：
每组测试数据输出一行判断结果，若输入的图为树，则输出“Case k is a tree.”，否则输出“Case k is not a tree.”其中k表示每组数据的编号（编号从1开始）。
样例输入：
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
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<cstdlib> 6 //int cmp(const void*a,const void*b) 7 //{ 8 // return(*(int *)a)<(*(int *)b)?1:-1; 9 //} 10 int f[1000000]; 11 int flag[1000000]; 12 int find(int x) 13 { 14 if(f[x]!=x) 15 f[x]=find(f[x]); 16 return f[x]; 17 } 18 19 int join(int x,int y) 20 { 21 int a=find(x); 22 int b=find(y); 23 if(b!=y) 24 return 1; 25 if(a==b) 26 return 1; 27 else 28 f[b]=a; 29 return 0; 30 } 31 32 int main() 33 { 34 int a,b; 35 int t=0,key=0,max=0,g=0,p=1; 36 memset(flag,0,sizeof(flag)); 37 for(int i=1;i<=999999;i++) 38 f[i]=i; 39 while(1) 40 { 41 scanf("%d%d",&a,&b); 42 if(a>max) 43 max=a; 44 if(b>max) 45 max=b; 46 if(a<=-1&&b<=-1) 47 break; 48 if(a==0&&b==0) 49 { 50 for(int i=1;i<=max;i++) 51 { 52 if(flag[i]==1&&f[i]==i) 53 g++; 54 } 55 if(key>0||g>=2) 56 printf("Case %d is not a tree. ",p++); 57 else 58 printf("Case %d is a tree. ",p++); 59 t=0;key=0;max=0;g=0; 60 memset(flag,0,sizeof(flag)); 61 for(int i=1;i<=999999;i++) 62 f[i]=i; 63 } 64 else 65 { 66 flag[a]=1; 67 flag[b]=1; 68 key+=join(a,b); 69 } 70 } 71 72 return 0; 73 }