poj1308 Is It A Tree?（并查集）详解

poj1308   http://poj.org/problem?id=1308

题目大意：输入若干组测试数据，输入 （-1 -1） 时输入结束。每组测试数据以输入（0 0）为结束标志。然后根据所给的所有（父亲， 孩子）数据对判断 是否能构成一棵树。

分析： 　都以了解树只有一个根节点，那么我们就判断是不是有多个树；又知道每个节点只有一个父亲节点，那么我们就判断他是不是构成环，成环则不是树。

注意：　①可以是空树；　②所给的节点构成森林（多个树）是不可以的，必须只能构成一棵树。

#include<iostream>

#include<cstdio>

#include<string.h>

using namespace std;

int out, flag, x, y, num, pre[];

int find(int a)//查找根节点

{

    int r, i, j;

    r = a; i = a;

    while(pre[r] != r)

        r = pre[r];

    while(pre[i] != r)

    {

        j = pre[i];

        pre[i] = r;

        i = j;

    }

    return r;

}

int main()

{

    num = ; out = ;

    while(out)

    {

        //先对所有节点的根节点进行初始化

        for(int i = ; i <= ; i++)

            pre[i] = i;

        flag = ;

        while(scanf("%d%d", &x, &y))

        {

            if(x ==  && y == )

                break;

            else if(x == - && y == -)

            {

                out = ;

                break;

            }

            int fx = find(x);

            int fy = find(y);

            //此处我们判断是否构成环

            //如果x和y的根节点相同，那么他们已经是属于同一棵树

            //若x又是y的父亲节点，那么将构成环

            if(fx == fy)

                flag = ;

            //如果x和y根节点不同，即不属于同一棵树， 那么将其合并成一棵树

            else if(fx != fy)

                pre[fy] = fx;

        }

        int k = ;

        //此处我们判断是不是森林，对所有节点(不包括没涉及的点)的根节点

        //进行统计，若不都一样那么说明存在多个跟， 有多颗树， 否则是一棵树。

        for(int i = ; i <= ; i++)

        {

            int ans = find(i);

            if(ans != i && k == )

                k = ans;

            else if(k !=  && ans != i)

            {

                if(ans != k)

                    flag = ;

            }

        }

        if(out ==  && flag == )

            printf("Case %d is not a tree.\n", ++num);

        else if(out ==  && flag == )

            printf("Case %d is a tree.\n", ++num);

    }

    return ;

}

杭电的1272 和这个题差不多  稍微改改就可以了。

#include<iostream>

#include<cstdio>

#include<string.h>

using namespace std;

int out, flag, x, y, pre[];

int find(int a)

{

    int r, i, j;

    r = a; i = a;

    while(pre[r] != r)

        r = pre[r];

    while(pre[i] != r)

    {

        j = pre[i];

        pre[i] = r;

        i = j;

    }

    return r;

}

int main()

{

    out = ;

    while(out)

    {

        for(int i = ; i <= ; i++)

        {

            pre[i] = i;

        }

        flag = ;

        while(scanf("%d%d", &x, &y))

        {

            if(x ==  && y == )

                break;

            else if(x == - && y == -)

            {

                out = ;

                break;

            }

            int fx = find(x);

            int fy = find(y);

            if(fx != fy)

            {

                pre[fx] = fy;

            }

            else if(fx == fy)

            {

                flag = ;

            }

        }

        int k = ;

        for(int i = ; i <= ; i++)

        {

            int ans = find(i);

            if(ans != i && k == )

                k = ans;

            else if(k !=  && ans != i)

            {

                if(ans != k)

                    flag = ;

            }

        }

        if(out ==  && flag == )

            printf("No\n");

        else if(out ==  && flag == )

            printf("Yes\n");

    }

    return ;

}