程序如下：
#include
const int max_num=100010;
typedef struct
{
int num,root,conn;//数据，根结点，入度
}Node;
Node node[max_num];
void init()//初始化
{
for(int i=0;i<max_num;i++)
{
node[i].conn=0;//入度初始化为0
node[i].root=i;//根结点为自身
node[i].num=0;//标记数字是否用过。0-没用过，1-用过
}
}
int find(int a)//寻找它的根节点
{
if(node[a].root!=a)
return node[a].root=find(node[a].root);
else
return node[a].root;
}
void merge(int a,int b)//合并
{
a=find(a),b=find(b);
if(a==b)//同一个根，说明在同一棵树里
return;
node[b].root=a;//把b的根结点赋给a的根结点，此时a已经是根结点
}
int main()
{
int n,m,i=1;
bool flag=true;
init();
while(scanf("%d%d",&n,&m)!=EOF&&n>=0&&m>=0)
{
if(!flag&&n!=0&&m!=0)continue;//判断是否是树
if(n==0&&m==0)//说明输入结束，开始处理吧
{
int root_num=0;
for(int j=1;j
{
//判断是否为森林。如果是，用root_num来记录根的数目
if(node[j].num&&find(j)==j)
root_num++;
if(node[j].conn>1)//如果出现某个节点的入度超过1，则不是树
{
flag=false;
break;
}
}
if(root_num>1)//连通分支大于1，是森林，不是树
flag=false;
if(flag)
printf("Case %d is a tree.\n",i++);
else printf("Case %d is not a tree.\n",i++);
init();//为下一个case处理进行初始化
continue;
}
if(m!=n&&find(n)==find(m)||m==n)
flag=false;
else
{
//将m,n记为结点
node[m].num=1;
node[n].num=1;
node[m].conn++;//入度加一
merge(n,m);
}
}
return 0;
}
