澳门威利斯人_威利斯人娱乐「手机版」

来自 办公软件 2019-11-16 06:37 的文章
当前位置: 澳门威利斯人 > 办公软件 > 正文

小希的迷宫

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卡塔 尔(英语:State of Qatar),现在她也想设计多个迷宫让Gardon来走。不过他设计迷宫的思路不平等,首先她以为具备的通道都应有是双向连通的,就是说假如有四个大路连通了房间A和B,那么既可以够经过它从房间A走到房间B,也得以透过它从房间B走到房间A,为了拉长难度,小希希望大肆五个屋企有且独有一条门路能够相同(除非走了回头路卡塔 尔(英语:State of Qatar)。小希未来把他的兼顾图给您,令你协理剖断她的设计图是还是不是相符他的宏图思路。举例下边包车型客车例证,前多少个是切合条件的,然而最终贰个却有两种办法从5达到8。
图片 1

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 贰零零陆-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="<<<

ACM 1272 小希的迷宫 小希的迷宫 Time Limit: 二零零四/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 3壹玖壹叁 Accepted Submission(s): 985...

本文由澳门威利斯人发布于办公软件,转载请注明出处:小希的迷宫

关键词: 澳门威利斯人