poj 1308 Is It A Tree?

点击打开链接poj 1308

思路：并查集
分析：如果是一棵树，那么就只能有唯一的一个根节点。所以我们只要在输入的时候判断两个元素能否合并即可，如果输入的两个元素的根节点相同肯定是不满足的，其它还有“空树”“森林”都不算是树。所以最后还要判断一下是否是森林还是树。注意句子末尾有个“.”

输入的边可能是自环，这个是一个trick

注意以下数据
1: 0 0 空树是一棵树。
2: 1 1 0 0 不是树 1 和 1的根据点相同
3: 1 2 1 2 0 0 不是树，第二个开始1 和 2的根节点相同不是树
4: 1 2 2 3 4 5 不是树 森林不算是树
5: 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1 最后的9 和1根节点相同不是树
6: 1 2 2 1 0 0 不是树

代码：

#include<set>
#include<cstdio>
#include<cstring>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 1000010;

int father[MAXN];
set<int>s;

void init(){
    s.clear();
    for(int i = 1 ; i < MAXN ; i++){
        father[i] = i; 
    }
}

int find(int x){
    if(father[x] != x)
        father[x] = find(father[x]);
    return father[x];
}

int main(){
    int cas = 1;
    int x , y;
    while(scanf("%d%d" , &x , &y) && x >= 0){
         printf("Case %d " , cas++);
         if(x+y == 0)
             puts("is a tree.");
         else{
             init(); 
             father[y] = x;
             // 如果出现自环的时候x == y的时候就不算树
             bool isOk = (y != x ? true : false);
             s.insert(x);
             s.insert(y);
             while(scanf("%d%d" , &x , &y) && x+y){
                 s.insert(x);
                 s.insert(y);
                 int fx = find(x);
                 int fy = find(y);
                 if(fy == fx){
                     isOk = false; 
                 } 
                 else{
                     father[fy] = fx; 
                 }
             } 
             if(!isOk)
                 puts("is not a tree.");
             else{
                 set<int>::iterator it = s.begin();
                 int root = find(*it);
                 for(it++; it != s.end() ; it++){
                     if(root != find(*it)){
                        isOk = false;
                        break;
                     } 
                 }
                 if(isOk)
                     puts("is a tree.");
                 else
                     puts("is not a tree.");
             }
         }
    }
    return 0;
}