学步园

思路：并查集思想，主要注意以下几组数据

1: 0 0 空树是一棵树


2: 1 1 0 0 不是树 不能自己指向自己

3: 1 2 1 2 0 0 不是树....自己开始一直在这么WA  好郁闷 重复都不行呀~~5555

4: 1 2 2 3 4 5 0 0 不是树  森林不算是树(主要是注意自己) 5: 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1  注意 一个节点在指向自己的父亲或祖先 都是错误的 即 9-->1 错


6: 1 2 2 1 0 0 也是错误的

#include <stdio.h>
#define M 10000
int a[M],b[M];
int flag;
int find (int v)
{
    int t;
    t = v;
    while (t !=
a[t])
       
t = a[t];
    return
t;
}
void Union (int x,int y)
{
    if (y !=
a[y])    
//如果结点编号不等于本身，说明有两条边指向它
    {
       
flag = 1;
       
return ;
    }
    int
v1,v2;
    v1 = find
(x);
    v2 = find
(y);
    if (v1 ==
v2)   
//两个点的根结点相等 说明形成了环或本身指向本身
    {
       
flag = 1;
       
return ;
    }
    if (v1 !=
v2)
       
a[v2] = v1;
}

int main ()
{
    int
x,y,i,j;
    int count =
1;

    while
(1)
    {
       
flag = 0;
       
j = 0;
       
for (i = 0; i < M; i ++)
           
a[i] = i;
       
scanf ("%d %d",&x,&y);
       
if (x == -1&&y == -1)
           
break;
       
if (x == 0&&y ==
0)    
//只有根结点
           
printf ("Case %d is a tree.\n",count++);

       
else
       
{
           
b[j++] =
x;           
//b数组存储 后面用来查找是否会形成森林
           
b[j++] = y;
           
Union (x,y);