https://blog.csdn.net/shengweisong/article/details/34099151

做了一上午，最终ac了 wa了一次主要是忘了还有环！。！

主要是运用并查集知识。又复习了一次！！

思路:输入之后找能不能成环，成环就不是，其次还要推断是不是有两个父节点，假设有两个父节点也不是。之后就找相关的祖先就好了。

还要注意：假设仅仅有一个节点，也是树。假设有两个或多个根节点也不是树；假设没有根节点也不是

链接

pid=1325" rel="nofollow">http://acm.hdu.edu.cn/showproblem.php?pid=1325

代码

#include<stdio.h>

int fat[1000];

int father( int n ) //寻找祖先

{

    if( fat[n] != n ) fat[n] = father(fat[n]);

    return fat[n];

}

int main()

{

    int i, j, n, m, a[1000], b[1000], v = 1;

    while( 1 ){

        for( i = 0; i < 1000; i ++ )

        fat[i] = i;

        int flag = 0;

        scanf( "%d%d", &a[0], &b[0] );

        if( a[0]< 0&&b[0]< 0 ) break;

        fat[b[0]] = a[0];//由题意可知fat[b[i]] = a[i]；

        i = 1;

        while( scanf("%d%d", &a[i], &b[i]), a[i]||b[i] ){

            if( flag == 0 ){ //假设flag=1那就表明成环了，或者有两个父节点

            	if( fat[a[i]] == b[i] ){

					flag = 1; //推断是不是成环

					continue;

				}

            	if( fat[b[i]] != b[i] ) {

					flag = 1;//推断是不是有两个父节点

					continue;

				}

            	if( fat[a[i]]!= a[i] )

            	fat[a[i]] = father(a[i]);

            	fat[b[i]] = a[i];

			}

			else{

				fat[b[i]] = a[i];

			}

			i++;

        }

       // for( j = 0; j < i; ++ j ) //以下四行没有必要，假设没有根节点。就是环（多亏了某仙鹤同学）

      //  if( fat[a[j]] == a[j] ) break;;

       // if( i == j  )

       // flag = 1;

        if( flag ){

             printf( "Case %d is not a tree.\n", v++ );

             continue;

        }

        else{

            if( i == 1 ){ //假设仅仅有一组

                 printf( "Case %d is a tree.\n", v++ );

                 continue;

            }

            for( j  = 1; j < i; ++ j ) //推断是不是有多个根节点

            if( fat[a[j]] != fat[a[0]] ){

                 printf( "Case %d is not a tree.\n", v++ );

                 break;

            }

            if( j == i )

             printf( "Case %d is a tree.\n", v++ );

        }

    }

    return 0;

}