#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
const int z=100010;
int exsit[z];
int root[z];
int time[z];
int w=0,u=1,num=0;
int j;
int count(int a,int b)
{
    if(exsit[a]==0)
    {

        w++;
        exsit[a]=1;
    }
    if(exsit[b]==0)
    {

        w++;
        exsit[b]=1;
    }
    return w;
}
void upset()
{
    for(int i=0; i<z; i++)
        root[i]=i;
}
int find(int a)
{
    return a==root[a]?a:root[a]=find(root[a]);
}
void unioner(int a,int b)
{
    int a1=find(a),b1=find(b);
    if(a1!=b1)
    {
        root[b]=a1;
        exsit[a1]=2;
        exsit[b1]=1;
    }
}
int main()
{
    int m,n;
    while(cin>>m>>n&&m>=0&&n>=0)
    {
        for(int i=0; i<z; i++)
        {
            exsit[i]=0;
            time[i]=0;
        }
        w=0;
        time[n]++;
        if(m>j)
            j=m;
        if(n>j)
            j=n;
        if(m==0)
        {
            printf("Case %d is a tree.\n",u);
            u++;
            continue;
        }
        //u++;//测试次数
        num=0;//边数
        num++;
        upset();


        w=count(m,n);
        unioner(m,n);
        int x,y;
        while(cin>>x>>y)
        {
            time[y]++;
            if(x>j)
                j=x;
            if(y>j)
                j=y;
            if(x==0&&y==0)
            {
                int t=0;
                for(int i=1; i<=j; i++)
                    if(time[i]>1)
                        t=1;
                if(t==1)
                    printf("Case %d is not a tree.\n",u);
                else if(num!=w-1)
                {
                    printf("Case %d is not a tree.\n",u);
                    u++;
                }
                else
                {
                    if(w==1)
                    {
                        printf("Case %d is not a tree.\n",u);
                        u++;
                    }
                    else
                    {
                        int p=0;
                        for(int i=1; i<=j; i++)
                        {
                            if(exsit[i]==2)
                                p++;
                        }
                        if(p!=1)
                        {
                            printf("Case %d is not a tree.\n",u);
                            u++;
                        }
                        else
                        {
                            printf("Case %d is a tree.\n",u);
                            u++;
                        }
                    }
                }
                break;
            }
            else
            {

                num++;
                count(x,y);
                unioner(x,y);

            }
        }
    }
}

• Re:最苦的不是空树。。。是大家给的数据都过了还是wa。。求指点QAQ (27) AlwaysLearning 2016-02-02 09:59:13