POJ 1308 Is It A Tree? （并查集）

链接：http://poj.org/problem?id=1308

思路：

1. 对每组输入的根节点标记表示这些节点出现过并进行并操作，并操作是两个节点不能有相同的根节点否则将构成环，假设b节点要接到a节点上，则要保证b节点是一个根节点；否则若进行并操作b将会有两个父节点，若无以上情况，则可以合并两棵树；

2. 每组数据输入结束时要计算整个图中的根节点的数目，若根节点的总数不为1，则构成的图不是一棵树；

3. 根据以上的判断就可以得到答案了，记得每组数据之后都要初始化数据；

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#define MAXN 1000005
#define RST(N)memset(N, 0, sizeof(N))
using namespace std;

int father[MAXN], flag[MAXN];   //标记数组；
int n, m, Max, key, cnt, cas = 1;

void Init()   //初始化；
{
    for(int i=1; i<=MAXN; i++) father[i] = i;
    RST(flag);
    Max = 0, key = 0, cnt = 0;
}

int Find(int x)   //寻找根节点；
{
    if(x != father[x]) {
        father[x] = Find(father[x]);
    }
    return father[x];
}

int Union(int x, int y)  //并操作；
{
    int fx = Find(x), fy = Find(y);
    if(fy != y) return 1;   //y连接到x上，要保证y是个根节点，否则y有两个父节点；
    if(fx == fy) return 1;  //如果x,y在同一棵树上，若在进行并操作就会产生环；
    else father[fy] = fx;  //若无以上两种操作，则合并x, y;
    return 0;
}

int main()
{

    Init();
    while(1) {
        scanf("%d %d", &n, &m);
        if(n < 0 && m < 0) break;
        if(n > Max) Max = n;
        if(m > Max) Max = m;
        if(n == 0 && m == 0) {
            for(int i=1; i<=Max; i++) {
                if(father[i] == i && flag[i]) cnt++;  //计算树根的数量是否大于2；
                if(cnt >= 2) break;
            }
            if(key > 0 || cnt >= 2) printf("Case %d is not a tree.\n", cas++);
            else printf("Case %d is a tree.\n", cas++);
            Init(); continue;   //每组测试数据之后初始化；
        }
        flag[n] = 1, flag[m] = 1;  //标记；
        key += Union(n, m);   //若出现不合法的情况，key的值会大于0；
    }
    return 0;
}

POJ 1308 Is It A Tree? （并查集）,布布扣,bubuko.com

POJ 1308 Is It A Tree? （并查集）

原文：http://blog.csdn.net/keshacookie/article/details/22808493