程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU ACM 1272 小希的迷宮

HDU ACM 1272 小希的迷宮

編輯：C++入門知識

HDU ACM 1272 小希的迷宮

小希的迷宮

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 31911 Accepted Submission(s): 9850

Problem Description 上次Gardon的迷宮城堡小希玩了很久（見Problem B），現在她也想設計一個迷宮讓Gardon來走。但是她設計迷宮的思路不一樣，首先她認為所有的通道都應該是雙向連通的，就是說如果有一個通道連通了房間A和B，那麼既可以通過它從房間A走到房間B，也可以通過它從房間B走到房間A，為了提高難度，小希希望任意兩個房間有且僅有一條路徑可以相通（除非走了回頭路）。小希現在把她的設計圖給你，讓你幫忙判斷她的設計圖是否符合她的設計思路。比如下面的例子，前兩個是符合條件的，但是最後一個卻有兩種方法從5到達8。

Input 輸入包含多組數據，每組數據是一個以0 0結尾的整數對列表，表示了一條通道連接的兩個房間的編號。房間的編號至少為1，且不超過100000。每兩組數據之間有一個空行。
整個文件以兩個-1結尾。

Output 對於輸入的每一組數據，輸出僅包括一行。如果該迷宮符合小希的思路，那麼輸出"Yes"，否則輸出"No"。

Sample Input

6 8  5 3  5 2  6 4
5 6  0 0

8 1  7 3  6 2  8 9  7 5
7 4  7 8  7 6  0 0

3 8  6 8  6 4
5 3  5 6  5 2  0 0

-1 -1

Sample Output

Yes
Yes
No

Author Gardon
Source HDU 2006-4 Programming Contest 操蛋，爆棧N次！並查集中要注意不一定非得用路徑壓縮！！結果寫了好幾個版本，原來是並查集函數的錯誤，其實這些個版本改動那一處全都能ac。首先發現可以利用並查集判斷無向圖回路，其次如果不存在回路，在它是連通圖的情況下，如果是一棵樹，那麼必然有結點數=邊數+1；注意前後邏輯。

#include
#include
#include
#include
using namespace std;
const int M=500004;
int F[M];
int cnt[M];
int Find(int x)
{
    int r=x;
    while(F[r]!=r)
        r=F[r];
    int k=x;
    while(k!=r)
    {
        int t=F[k];
        F[k]=r;
        k=t;
    }
    return r;
}

bool Is_same(int x,int y)
{
    return Find(x)==Find(y);
}

void union_set(int x , int y)
{
    int tx=Find(x);
    int ty=Find(y);
    if(tx!=ty)
    {
        F[tx]=ty;
    }

}

int main()
{
    int flag1=0;
    int a,b;
loop:
    for(int j=0; jdict;
    int flag2=0;
    memset(cnt,0,sizeof(cnt));
    int MM=-1,MII=9999999;
    cin>>a>>b;
    if((a==-1)&&(b==-1))
        return 0;
    else if(a==0&&b==0)
    {
        cout<<"Yes"<MM)
            MM=a;
        if(b>MM)
            MM=b;
        if(a>a>>b,a+b)
    {
        if(!cnt[a])
            aa++;
        if(!cnt[b])
            aa++;
        count++;
        cnt[a]=1;
        cnt[b]=1;
        if(a>MM)
            MM=a;
        if(b>MM)
            MM=b;
        if(a

或著：#include
#include
#include
using namespace std;
const int M=100004;
int F[M];

int Find(int x)
{
    int r=x;
    while(F[r]!=r)
        r=F[r];
    int k=x;
    while(k!=r)
    {
        int t=F[k];
        F[k]=r;
        k=t;
    }
    return r;
}

bool Is_same(int x,int y)
{
    return Find(x)==Find(y);
}

void union_set(int x , int y)
{
    int tx=Find(x);
    int ty=Find(y);
    if(tx!=ty)
    {
        F[tx]=ty;
    }
}

int main()
{
    setdict;
    int flag1=0;
    for(int j=0; j>a>>b,a+b)
    {
        flag=1;
        if((a==-1)&&(b==-1))
            return 0;

        dict.insert(a);
        dict.insert(b);

        if(Is_same(a,b))
            flag1=1;
        union_set(a,b);
    }
    if(!flag)
    {
        cout<<"Yes"< ::iterator it=dict.begin();
    int f0=Find(*it);
    it++;
    for(; it!=dict.end(); it++)
    {
        if(Find(*it)!=f0)
            flag2=1;
    }
    //cout<<"flag="<