Poj Solution 1308

http://poj.org/problem?id=1308

#include<iostream>
using namespace std;
short ins[50000];
bool bb[50000];
int main()
{
    int a,b,c=1;
    int i;
    memset(bb,0,sizeof(bb));
    memset(ins,0,sizeof(ins));
    int iMax=-1;
    int zero;
    bool flag;// ones;

    while(scanf("%d%d",&a,&b))
    {
        if(a==-1 && b==-1)
            break;
        if(a==0 && b==0)
        {
            zero=0;
            flag = false;
            
            for(i=1;i<=iMax;++i)
            {
                if(bb[i])
                {
                    if(ins[i]==0)
                        
                        zero+=1;
                    else
                    {
                        if(ins[i]>1)
                        {
                            printf("Case %d is not a tree.n",c);
                            c++;
                            flag=true;
                            break;
                        }
                    }
                    if(zero > 1)//度为0的点大于1个

                    {
                        printf("Case %d is not a tree.n",c);
                        c++;
                        flag=true;
                        break;
                    }
                }
            }
            if(flag == false )
            {
                if(zero ==0 && iMax!=-1)
                    printf("Case %d is not a tree.n",c);
                else
                    printf("Case %d is a tree.n",c);
                c++;
            }
            memset(bb,0,sizeof(bb));
            memset(ins,0,sizeof(ins));
            iMax=-1;
        }
        else
        {
            bb[a]=true;
            bb[b]=true;
            ins[b]+=1;
            if(iMax<a)
                iMax=a;
            if(iMax<b)
                iMax=b;
        }
    }
    return 0;
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *