hdu 1325 Is It A Tree?

题目链接

#include"stdio.h"
int set[1001],v[1001],cnt[10001],flag;
//初始化
void fun()
{
	int i;
	flag=1;
	for(i=1;i<=1000;i++)
	{
		set[i]=i;
		v[i]=0;
		cnt[i]=0;
	}
}
//查找根节点
int find(int x)
{
	return x==set[x]?x:find(set[x]);
}
int judge()
{
	int i,t;
	for(i=1;i<=1000;i++)
	{
		if(v[i]) 
			cnt[find(i)]++;//如果只有一棵树的话，只能有一个根节点。
	}
	t=0;
	for(i=1;i<=1000;i++)
		if(cnt[i]>1) t++;//t计算根节点数目
		if(t!=1) return -1;
		else return 1;
}
int main()
{
	int a,b,i,count;
	count=0;
	fun();
	while(scanf("%d%d",&a,&b)!=EOF)
	{
		if(a<0) break;
		if(a==0&&b==0)
		{
			count++;
			if(flag==0)
				printf("Case %d is not a tree.\n",count);
			else
			{
				if(judge()==1)
					printf("Case %d is a tree.\n",count);
				else
					printf("Case %d is not a tree.\n",count);
			}
			fun();
		}
		v[a]=v[b]=1;
		if(find(a)==find(b)||find(set[b])!=b)//判断是否有环以及一个节点是否有多个根节点。
			flag=0;
		else set[b]=a;//合并
	}
	return 0;
}