程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 並查集 poj1308 hd1272

並查集 poj1308 hd1272

編輯:C++入門知識

並查集 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;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved