step1:对输入的节点标记并进行合并操作。合并时两个节点不能有相同的根节点,否则会构成环。若b要接到a上,保证b是根节点,否则b将会有两个父节点。若无以上两种情况,可以合并两棵树。
step2:每组数据输入结束后要计算根节点的总数,若根节点总数不为1,则构成的不是树。
step3:根据以上判断输出结果,每组数据输出后要初始化数据。
http://poj.org/problem?id=1308
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 int f[1000000],flag[1000000]; 5 int find(int x) 6 { 7 if(f[x]!=x) 8 f[x]=find(f[x]); 9 return f[x]; 10 } 11 int make(int a,int b) //并操作错误返回1,正确返回0 12 { 13 int f1=find(a); 14 int f2=find(b); 15 if(f2!=b) //保证b节点是根节点,否则有两个父节点 16 return 1; 17 if(f1==f2) //保证a,b不在同一棵树中,避免产生环 18 return 1; 19 else
20 f[f2]=f1; //合并 21 return 0; 22 } 23 int main() 24 { 25 int a,b,m=0,t=0,i,p=1,key=0; 26 for(i=1;i<=999999;i++) 27 f[i]=i; 28 memset(flag,0,sizeof(flag)); 29 while(1) 30 { 31 scanf("%d%d",&a,&b); 32 if(a<=-1&&b<=-1) break; 33 if(a>m) m=a; 34 if(b>m) m=b; 35 if(a==0&&b==0) 36 { 37 for(i=1;i<=m;i++) //计算树根的数量是否大于1 38 { 39 if(flag[i]==1&&f[i]==i) 40 t++; 41 if(t>=2) break; 42 } 43 if(key>0||t>=2) 44 printf("Case %d is not a tree.\n",p++); 45 else
46 printf("Case %d is a tree.\n",p++); 47 for(i=1;i<=999999;i++) 48 f[i]=i; 49 m=0,t=0,key=0; 50 memset(flag,0,sizeof(flag)); 51 continue; 52 } 53 flag[a]=1;flag[b]=1; 54 key+=make(a,b); 55 } 56 return 0; 57 }