NYOJ129 树的判定 || POJ1308 Is It A Tree? 【并查集应用,树的定义】

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 04 月 06 日

http://acm.nyist.net/JudgeOnline/problem.php?pid=129

一个有向图入度为1的节点仅有一个,并且无环,则是一颗树。

#include<cstdio>  
#include <cstring>  
using namespace std;  
const int MAXSIZE = 10002;    
int pre[MAXSIZE]; //根节点i,pre[i] = -num,其中num是该树的节点数目;    
//非根节点j,pre[j] = k,其中k是j的父节点    
int Find(int x){//查找+非递归的路径压缩    
    int p = x;    
    while( pre[p] > 0 )    p = pre[p];    
    while( x != p ){    
        int temp = pre[x]; pre[x] = p; x = temp;    
    }    
    return x;    
}    
void Union(int r1, int r2){    
    int a = Find(r1); int b = Find(r2);    
    if( a == b ) return ;    
    //加权规则合并    
    if( pre[a] < pre[b] ){    
        pre[a] += pre[b]; pre[b] = a;    
    }    
    else {    
        pre[b] += pre[a]; pre[a] = b;    
    }    
}    
void Initi(void)    
{    
    for( int i=0; i < MAXSIZE; ++i ) pre[i] = -1;    
}    
int treeEs[MAXSIZE];  
int main(){  
    //freopen("1.txt","r",stdin);  
    int begin,end,flag=1,n=1;  
    Initi();  
    memset(treeEs,-1,sizeof(treeEs));  
    while(scanf("%d%d",&begin,&end))  
    {  
        if(begin==-1 && end==-1) break;  
        if(begin==0 && end==0){  
            int enternum=0;  
            for (int i=0;i<MAXSIZE;i++)  
            {  
                if(treeEs[i]==0) enternum++;  
            }  
            if(enternum>1) flag=0;  
            if(flag)   
                printf("Case %d is a tree.\n",n++);  
            else printf("Case %d is not a tree.\n",n++);  
            memset(treeEs,-1,sizeof(treeEs));  
            flag=1;  
            Initi();  
        }  
        else{  
            if(flag==0) continue;  
            if(Find(begin)==Find(end)) flag=0;  
            else{  
                if(treeEs[begin]<0) treeEs[begin]=0;  
                if(treeEs[end]<0) treeEs[end]=0;  
                treeEs[end]++;  
                Union(begin,end);  
            }  
        }  
    }  
} 

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期六, 2017 年 10 月 21 日