首页 > 其他 > 详细

hdoj 1325 Is It A Tree? 【并查集】

时间:2014-06-24 17:17:40      阅读:350      评论:0      收藏:0      [点我收藏+]

做了一上午,终于ac了 wa了一次主要是忘了还有环!!! 

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

思路:输入之后找能不能成环,成环就不是,其次还要判断是不是有两个父节点,如果有两个父节点也不是,之后就找相关的祖先就好了;

还要注意:如果只有一个节点,也是树,如果有两个或多个根节点也不是树;如果没有根节点也不是

链接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;
} 


hdoj 1325 Is It A Tree? 【并查集】,布布扣,bubuko.com

hdoj 1325 Is It A Tree? 【并查集】

原文:http://blog.csdn.net/shengweisong/article/details/34099151

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!