並查集 poj1308 hd1272

並查集 poj1308 hd1272

題目大意：輸入若干組測試數據，輸入 （-1 -1） 時輸入結束。每組測試數據以輸入（0 0）為結束標志。然後根據所給的所有（父親， 孩子）數據對判斷 是否能構成一棵樹。

分析： 　都以了解樹只有一個根節點，那麼我們就判斷是不是有多個樹；又知道每個節點只有一個父親節點，那麼我們就判斷他是不是構成環，　成環則不是樹。

注意：　①可以是空樹；　②所給的節點構成森林（多個樹）是不可以的，必須只能構成一棵樹。

#include
#include
#include
using namespace std;

int out, flag, x, y, num, pre[10010];
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 = 0; out = 1;
    while(out)
    {
        //先對所有節點的根節點進行初始化
        for(int i = 1; i <= 10000; i++)
            pre[i] = i;

        flag = 1;
        while(scanf(%d%d, &x, &y))
        {
            if(x == 0 && y == 0)
                break;
            else if(x == -1 && y == -1)
            {
                out = 0;
                break;
            }
            int fx = find(x);
            int fy = find(y);
            //此處我們判斷是否構成環
            //如果x和y的根節點相同，那麼他們已經是屬於同一棵樹
            //若x又是y的父親節點，那麼將構成環
            if(fx == fy)
                flag = 0;
            //如果x和y根節點不同，即不屬於同一棵樹， 那麼將其合並成一棵樹
            else if(fx != fy)
                pre[fy] = fx;
        }
        int k = 0;
        //此處我們判斷是不是森林，對所有節點(不包括沒涉及的點)的根節點
        //進行統計，若不都一樣那麼說明存在多個跟， 有多顆樹， 否則是一棵樹。
        for(int i = 1; i <= 10000; i++)
        {
            int ans = find(i);
            if(ans != i && k == 0)
                k = ans;
            else if(k != 0 && ans != i)
            {
                if(ans != k)
                    flag = 0;
            }
        }
        if(out == 1 && flag == 0)
            printf(Case %d is not a tree.
, ++num);
        else if(out == 1 && flag == 1)
            printf(Case %d is a tree.
, ++num);
    }
    return 0;
}

杭電的1272 和這個題差不多  稍微改改就可以了。

#include
#include
#include
using namespace std;

int out, flag, x, y, pre[100010];
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 = 1;
    while(out)
    {
        for(int i = 1; i <= 100000; i++)
        {
            pre[i] = i;
        }
        flag = 1;
        while(scanf(%d%d, &x, &y))
        {
            if(x == 0 && y == 0)
                break;
            else if(x == -1 && y == -1)
            {
                out = 0;
                break;
            }
            int fx = find(x);
            int fy = find(y);
            if(fx != fy)
            {
                pre[fx] = fy;
            }
            else if(fx == fy)
            {
                flag = 0;
            }
        }
        int k = 0;
        for(int i = 1; i <= 100000; i++)
        {
            int ans = find(i);
            if(ans != i && k == 0)
                k = ans;
            else if(k != 0 && ans != i)
            {
                if(ans != k)
                    flag = 0;
            }
        }
        if(out == 1 && flag == 0)
            printf(No
);
        else if(out == 1 && flag == 1)
            printf(Yes
);
    }
    return 0;
}