现在的位置: 首页 > 综合 > 正文

poj 1308 Is It A Tree? (并查集)

2012年05月13日 ⁄ 综合 ⁄ 共 1427字 ⁄ 字号 评论关闭

题意:给出一些节点的连接情况,问所给出的节点是不是可以构成一棵树。

树的定义已经给出:

1. 只有一个根节点

2. 根节点到每个节点只有唯一路径

3. 题目第一句特别提到空树也是一颗合法树

对于第一条,明显的森林不是树,并查集将每对输入合并,最后看是否在同一个集合中。

第二条,保证唯一路径与题目中给出的第二条定义相似,对于每个节点,只有一条边指向它。如果节点已经存在于集合中,则肯定已经有一边指向它,或者它是作为根节点。也就是说,输入的两个元素不能在同一个集合中。可恶的是这题居然没给数据量!开始以200为上限做的,最后用majia试了下数据范围,竟然只有15。。。太坑了...

code:

#include<cstdio>
int p[16], data[32] ;
void make_set(){
    for(int i=0; i<101; i++)
        p[i] = i ;
}
int find_set(int x){
    if(x!=p[x])
        p[x] = find_set(p[x]) ;
    return p[x] ;
}
void union_set(int x, int y){
    x = find_set(x) ;
    y = find_set(y) ;
    if(x!=y)
        p[y] = x ;
}
int main(){
    int x, y, t=1, count ;
    bool flag ;
    while(~scanf("%d%d", &x, &y)&&(x+y)>=0){
        flag = true ;
        count = 0 ;
        data[count++] = x ;
        data[count++] = y ;
        if(x==0&&y==0){
            printf("Case %d is a tree.\n", t++) ;
            continue ;
        }
        make_set() ;
        if(x==y)    flag = false ;
        union_set(x, y) ;
        while(~scanf("%d%d", &x, &y)&&(x+y)){
            if(find_set(x)==find_set(y))    flag = false ;
            union_set(x, y) ;
            data[count++] = x ;
            data[count++] = y ;
        }
        for(y=1; y<count; y++)
            if(find_set(data[0])!=find_set(data[y]))
                flag = false ;
        if(flag)    printf("Case %d is a tree.\n", t ++) ;
        else    printf("Case %d is not a tree.\n", t ++);
    }
    return 0 ;

 

 

抱歉!评论已关闭.