POJ 1308 Is It A Tree 解题报告

时间：2010-06-02 来源：华南理工大学

一、问题描述

http://acm.pku.edu.cn/JudgeOnline/problem?id=1308

二、解题思路

用一个数据保存节点的入度，一个数组表示该编号的节点是否已经过。然后遍历一次数组，如果入度为0的节点只有一个，其他都是入度为1的节点，那么就是一棵树，否则不是一棵树。

三、代码

#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;
}