题意：给你许多点,分别链接起来，问你这是否为一棵树.（输入0 0 结束本组输入，输入-1 -1结束程序运行）
思路：要判断是否为一棵树,两点要注意,一是要是一颗,不能是多颗,二是该树中不能有环,我们的主要任务是就是判断这两点,注意,空树也符合条件,具体方法看代码（代码中也有注释）
#include<cstdio>
#include<cstring>
const int maxn=1005;
int father[maxn],ans[maxn];
int Find(int x)
{
if(father[x]<0) return x;
return Find(father[x]);
}
void Union(int m,int n)
{
int x=Find(m);
int y=Find(n);
int tmp=father[x]+father[y];
if(father[x]>father[y])
{
father[x]=y;
father[y]=tmp;
}
else
{
father[y]=x;
father[x]=tmp;
}
}
int main()
{ int cnt=1,a,b;
while(1)
{ memset(ans,0,sizeof(ans));//初始化两个数组
memset(father,-1,sizeof(father));
scanf("%d %d",&a,&b);
if(a==0 && b==0 ){//特判为空树的情况.
printf("Case %d is a tree.\n",cnt++);
continue;
}
if(a==-1 && b==-1)//输入-1 -1时结束运行.
break;
Union(a,b);//分别把每两个点连接起来.
ans[a]=1,ans[b]=1;//用于保存一共连接了好多节点,后面用于判断是否为一棵树的用处.
while(1)
{
scanf("%d %d",&a,&b);
if(a==0 && b==0)
break;
Union(a,b);//效果如上.
ans[a]=1,ans[b]=1;
}
int cnt1=0,minx=0;
for(int i=1;i<maxn;i++){
if(ans[i])
cnt1++;//cnt1记录保存了好多个节点,
if(father[i]<minx)
minx=father[i];//记录最大的一棵树上有好多个节点
}
if(minx==-1*cnt1)//如果节点相同则就符合条件.(因为如果该树中有环则minx一定是小于-1*cnt1的,可以根据该程序推一推就知道了)
printf("Case %d is a tree.\n",cnt++);
else
printf("Case %d is not a tree.\n",cnt++);
}
}
