} } }

    hdu1272 小希的迷宫

    添加时间:2013-7-26 点击量:

    小希的迷宫


    http://acm.hdu.edu.cn/showproblem.php?pid=1272


    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

    首要断定

    1.  边数=点数-1

    2.  是否连通

    3.  当输入的是 0 0 时辰,输出时Yes












    #include<iostream>
    
    #include
    <string.h>
    #include
    <stdio.h>
    using namespace std;
    int father[101000],p[101000];
    void Make(int x)
    {
    father[x]
    =x;
    }
    int find(int x)
    {
    int r=x,t;
    while(r!=father[r])
    {
    r
    =father[r];
    }
    while(x!=r)
    {
    t
    =father[x];
    father[x]
    =r;
    x
    =father[x];
    }
    return r;
    }
    void Union(int a,int b)
    {
    a
    =find(a);
    b
    =find(b);
    if(a!=b)
    father[a]
    =b;
    }
    int main()
    {
    int a,b,sum,i,j,sum2,time=1;
    while(cin>>a>>b)
    {
    if(a==0&&b==0
    {
    cout
    <<Yes<<endl;
    continue;
    }

    for(i=1;i<=100000;i++
    Make(i);
    sum
    =sum2=0;
    memset(p,
    0sizeof(p));
    if(a==-1&&b==-1
    break;
    sum
    ++;
    p[a]
    =1;p[b]=1;
    Union(a,b);
    while(cin>>a>>b)
    {
    if(a==0&&b==0
    break;
    p[a]
    =1;p[b]=1;
    Union(a,b);
    sum
    ++;
    }
    getchar();getchar();
    for(i=0;i<=100000;i++
    if(p[i]!=0
    sum2
    ++;
    if(sum!=sum2-1
    cout
    <<No<<endl;
    else
    {
    int t,k=0;
    for(i=1;i<=100000;i++
    if(p[i]!=0
    {
    t
    =find(i);
    break;
    }
    for(i=1;i<=100000;i++
    if(p[i]!=0
    {
    if(find(i)!=t)
    {
    cout
    <<No<<endl;
    k
    =1;
    break;
    }
    }
    if(k==0
    cout
    <<Yes<<endl;
    }
    }
    }


    View Code



    分享到: