POJ 1300 Door Man(欧拉回路判定)

POJ 1300 Door Man(欧拉回路判定)

http://poj.org/problem?id=1300

题意:给你N个房间(图节点)以及房间之间的门(图的边),且给你初始的房间号M,问你从初始房间走,可不可以经过每个门仅1次,最后到达0号房间.且所有的门都被你走过1次?

分析:仔细一看,其实这个问题就是判定是否存在无向图的欧拉回路或通路的问题.本题要理清所有可能的情况,理清了之后就很简单.

首先要求所有门都被走一遍,所以任何有门的房间都必须是在同一连通分量:表现为degree不为0的节点所属并查集唯一.(因为允许存在孤立的一点,房间)

第二,如果所有点的degree都为偶数,那么该图的连通部分存在欧拉回路.(最终要求在0点结束)所以此时要求M也为0,否则不可能在0结束.

第三,如果所有点中有2个点的degree为奇数,要求这两个点一个为0,一个为M.否则不存在欧拉通路.

至于当存在欧拉路时,从M需要走多少条边到0房间呢?肯定是走过所有的边了,所有边数==总度数/2.

(POJ这里的数据可能有点弱,没考虑连通分量的代码也能AC)

AC代码:

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=20+5;
int m,n;
int sum;//总度数
int degree[maxn];
int fa[maxn];
int findset(int i)
{
    if(fa[i]==-1) return i;
    return fa[i]=findset(fa[i]);
}
int main()
{
    char str[200];
    while(scanf("%s",str)==1&& str[0]=='S')
    {
        sum=0;
        memset(fa,-1,sizeof(fa));
        memset(degree,0,sizeof(degree));

        scanf("%d%d",&m,&n);//处理输入
        getchar();//读回车
        for(int i=0;i<n;i++)
        {
            gets(str);
            int len=strlen(str);
            if(len==0) continue;
            int num=0;//读取当前str中的数
            for(int j=0;j<=len;j++)
            {
                if(str[j]==' '||str[j]==0)//说明之前已经读了一个数在num中
                {
                    degree[num]++;
                    degree[i]++;
                    sum+=2;
                    int pa=findset(i), pb=findset(num);
                    if(pa!=pb) fa[pa]=pb;
                    num=0;
                }
                else
                {
                    num = num*10+str[j]-'0';
                }
            }
        }
        gets(str);//读入末尾的END

        if(findset(0)!=findset(m))//0点与m点不通
        {
            printf("NO\n");
            continue;
        }

        int cnt=0;//只能有一个连通分量
        for(int i=0;i<n;i++)if(degree[i])
            cnt += findset(i)==i?1:0;
        if(cnt>1)
        {
            printf("NO\n");
            continue;
        }

        cnt=0;//记录奇数度的点个数
        for(int i=0;i<n;i++) cnt += degree[i]%2==1 ? 1:0;
        if(cnt==0 && m==0)//欧拉回路
            printf("YES %d\n",sum/2);
        else if(cnt==2 && m!=0 && degree[0]%2==1 && degree[m]%2==1)//欧拉通路
            printf("YES %d\n",sum/2);
        else//其他非法情况
            printf("NO\n");
    }
    return 0;
}

下面这份代码也能在POJ AC,但是缺根本没考虑图连通的问题,是有缺陷的:

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=20+5;
int m,n;
int sum;//总度数
int degree[maxn];
int fa[maxn];
int findset(int i)
{
    if(fa[i]==-1) return i;
    return fa[i]=findset(fa[i]);
}
int main()
{
    char str[200];
    while(scanf("%s",str)==1&& str[0]=='S')
    {
        sum=0;
        memset(fa,-1,sizeof(fa));
        memset(degree,0,sizeof(degree));

        scanf("%d%d",&m,&n);//处理输入
        getchar();//读回车
        for(int i=0;i<n;i++)
        {
            gets(str);
            int len=strlen(str);
            if(len==0) continue;
            int num=0;//读取当前str中的数
            for(int j=0;j<=len;j++)
            {
                if(str[j]==' '||str[j]==0)//说明之前已经读了一个数在num中
                {
                    degree[num]++;
                    degree[i]++;
                    sum+=2;
                    int pa=findset(i), pb=findset(num);
                    if(pa!=pb) fa[pa]=pb;
                    num=0;
                }
                else
                {
                    num = num*10+str[j]-'0';
                }
            }
        }
        gets(str);//读入末尾的END

        int cnt=0;//记录奇数度的点个数
        for(int i=0;i<n;i++) cnt += degree[i]%2==1 ? 1:0;
        if(cnt==0 && m==0)//欧拉回路
            printf("YES %d\n",sum/2);
        else if(cnt==2 && m!=0 && degree[0]%2==1 && degree[m]%2==1)//欧拉通路
            printf("YES %d\n",sum/2);
        else//其他非法情况
            printf("NO\n");
    }
    return 0;
}