http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=357#problem/B
这是一道简单的并查集题,最终判断能否形成树要看是否有回路和根节点相同

#include<stdio.h>
#define MAX 100005
int fa[MAX],flag[MAX];
void init(){//初始化
    int i;
    for(i=1;i<=MAX;i++){
        flag[i-1]=0;
        fa[i]=i;
    }
}
int find(int p){//查找父结点
    if(p!=fa[p])
        p=find(fa[p]);
    return p;
}
int Union(int a,int b){//合并
    int pa=find(a),pb=find(b);
    if(pa!=pb){
        fa[pb]=pa;
        return 1;
    }
    else
        return 0;
}
int main(){
    int n=1,m,i,a,b,t=1,f,father;
    while(1){
        init();
        while(scanf("%d%d",&a,&b)!=EOF){
            if(a==-1||a==0)
                break;
            flag[a]=flag[b]=1;//给已输入的数字记为一,未出现的在初始化后始终为零
            f=Union(a,b);
            if(f==0)//两点有相同父结点且该两点还有父子关系
                t=0;//不构成树
        }
        if(a==-1)
            break;
        if(a==0){//判断父结点是否相同
            for(i=1;i<=MAX;i++)
                if(flag[i])
                    father=find(i);
            for(i=1;i<=MAX;i++)
                if(flag[i]&&father!=find(i)){
                    t=0;
                    break;
                }
        if(t)
            printf("Case %d is a tree.\n",n++);
        else
            printf("Case %d is not a tree.\n",n++);
        t=1;
    }
    }
    return 0;
}


发表评论

电子邮件地址不会被公开。

Post Navigation