In this problem you will be given several descriptions of collections of nodes connected by directed edges. For each of these you are to determine if the collection satisfies the definition of a tree or not.
Input
The input will consist of a sequence of descriptions (test cases) followed by a pair of negative integers. Each test case will consist of a sequence of edge descriptions followed by a pair of zeroes Each edge description will consist of a pair of integers; the first integer identifies the node from which the edge begins, and the second integer identifies the node to which the edge is directed. Node numbers will always be greater than zero.
Output
For each test case display the line "Case k is a tree." or the line "Case k is not a tree.", where k corresponds to the test case number (they are sequentially numbered starting with 1).
Sample Input
6 8 5 3 5 2 6 45 6 0 0
8 1 7 3 6 2 8 9 7 57 4 7 8 7 6 0 0
3 8 6 8 6 45 3 5 6 5 2 0 0
-1 -1
Sample Output
Case 1 is a tree.
Case 2 is a tree.
Case 3 is not a tree.
别看这道题的英文复杂，实际上题意真的简单，题意如下：
就样例来说，每两个数字代表一条边的两端，也就是说这两个数字代表一条边，0 0代表一组数据的结束，-1 -1代表程序结束。
这一道题的目的就是为了判断一下这些数字到底能不能组成一棵树。
我们要知道，要组成一颗树呢，首先，要没有环（你见过一颗树有环的吗，反正我是没有），其次，这棵树只能有一个根节点（有两个及以上的根节点，这就不是树了，是森林了），最后，一个点的入度最多为1（如果入度大于1了，那这些数构成的不是有森林就是有环了），根节点入度为0。
还有，我们要注意一个坑点，空树也是一棵树，也就是说直接给你一个0 0，这就是一个树。
你们可能注意到我的写法里面用了一下宏定义，其实适当的运用宏定义不仅使得代码的意思更好理解，还可以优化我们的代码。
这道题呢我是用并查集做的，不用并查集其实也能做。
代码如下：
#include<cstdio>
#include<iostream>
#include<cstring>
#define cls(x) memset(x,0,sizeof(x))//代表清空一个数组
using namespace std;
const int MAXN=100010;
const int inf=1<<29;
bool flag=false;
int Min,Max;//这里的Min和Max代表得是点的大小范围
int par[MAXN],in[MAXN];
bool exi[MAXN];//判断一个点是否存在
int find(int x)
{
if(par[x]==x)return x;
return par[x]=find(par[x]);
}
void init()
{
for(int i=1;i<=MAXN;i++)
par[i]=i;
}
void unite(int x,int y)
{
x=find(x);
y=find(y);
if(x==y){
flag=true;//判断是否有环
return ;
}
par[y]=x;
}
bool solve()
{
int cnt=0;
for(int i=Min;i<=Max;i++)
if(exi[i])
{
if(in[i]==0)cnt++;//判断根结点
if(in[i]>1)return false;//判断是否有入度大于1的点
}
if(cnt!=1)return false;
return true;
}
int main()
{
int a,b;
Min=inf,Max=-1;
int p=1;
init();
while(~scanf("%d%d",&a,&b))
{
if(a==-1&&b==-1)return 0;
if(a==0 && b==0)
{
if(Min==inf&&Max==-1){
printf("Case %d is a tree.\n",p++);
continue;
}
bool ans=solve();
if(ans && !flag)printf("Case %d is a tree.\n",p++);
else printf("Case %d is not a tree.\n",p++);
cls(in);
cls(par);
cls(exi);
Min=inf;
Max=-1;
init();
flag=false;
continue;
}
in[b]++;
if(Max<a)Max=a;//确定点范围
if(Max<b)Max=b;
if(Min>a)Min=a;
if(Min>b)Min=b;
exi[a]=true;
exi[b]=true;
unite(a,b);
}
return 0;
}
