2017-01-16 新生训练题G题菜鸟微见解

题意：给你许多点,分别链接起来，问你这是否为一棵树.（输入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++);
    }
}