题意：判断这是不是一棵树。
思路：这个题还是有部分坑点的。首先空树也是一棵树，还有森林不是树。
关于森林的判断我是利用并查集把每一个点压缩路径，看一共有几个原始点，超过一个，则不是树是森林。
关于并查集
寻找以及压缩的代码
1 int Find(int x) 2 { 3 int _b,int _x=x; 4 while(belg[_x]!=_x) //压缩路径，找到它的最顶端的点。 5 { 6 _x=belg[_x]; 7 } 8 while(belg[x]!=x) //把这一系列的点的父亲节点都更新到最顶端的点。 9 {10 _b=belg[x];11 belg[x]=_x;12 x=_b;13 }14 return _x;15 }
关于合并
1 int Union(int i,int j) 2 { 3 if(rand()&1) //随机分配 4 { 5 belg[j]=i; 6 } 7 else 8 { 9 belg[i]=j;10 }11 }
1 #include2 #include 3 #include 4 #define l 10010 5 6 using namespace std; 7 8 int belg[l]; 9 10 int fin(int x)11 {12 int _b,_x=x;13 while(belg[_x]!=_x&&belg[_x])14 {15 _x=belg[_x];16 }17 while(belg[x]!=x&&belg[x])18 {19 _b=belg[x];20 belg[x]=_x;21 x=_b;22 }23 return _x;24 }25 26 int main()27 {28 // freopen("in.txt","r",stdin);29 //freopen("out.txt","w",stdout);30 int m,n,ans,cas,father;31 bool mark[l];32 cas=0;33 while(scanf("%d%d",&m,&n),m!=-1||n!=-1)34 {35 ans=1,father=0;36 memset(belg,0,sizeof(belg));37 memset(mark,false,sizeof(mark));38 belg[n]=m;39 mark[n]=true;40 if(m==n&&m!=0) ans=0;41 if(m==n&&m==0) ans=1;42 else while(scanf("%d%d",&m,&n),m||n)43 {44 if(belg[m]==n) {ans=0;continue;}45 if(belg[n]) ans=0;46 if(n==m) ans=0;47 if(!belg[n]&&n!=m) belg[n]=m;48 fin(n);49 mark[n]=true;50 }51 for(int i=0;i<100;i++)52 if(mark[i]) fin(i);53 for(int i=0;i<100;i++)54 {55 if(father==0&&mark[i]) {father=belg[i];continue;}56 if(mark[i]&&belg[i]!=father) {57 ans=0;58 break;59 }60 }61 if(ans) printf("Case %d is a tree.\n",++cas);62 else printf("Case %d is not a tree.\n",++cas);63 }64 return 0;65 }
测试数据：
1 2 2 3 3 1 5 6 0 00 00 01 2 3 4 4 5 5 3 0 02 1 3 1 4 1 5 1 0 02 1 3 1 4 1 0 01 2 4 5 5 4 0 01 2 1 3 1 4 1 5 0 0-1 -1
答案
Case 1 is not a tree.
Case 2 is a tree.
Case 3 is a tree. Case 4 is not a tree. Case 5 is not a tree. Case 6 is not a tree. Case 7 is not a tree. Case 8 is a tree.