POJ--1300--Door Man【推断无向图欧拉通路】

题意：有n个房间。每一个房间有若干个门和别的房间相连。管家从m房间開始走。要回到自己的住处（0），问是否有一条路能够走遍全部的门而且没有反复的路。

无向图欧拉通路充要条件：G为连通图，而且G仅有两个奇度结点（度数为奇数的顶点）或者无奇度结点。

无向图欧拉回路充要条件：G为无奇度结点的连通图。

思路：推断是否存在欧拉通路。依据欧拉通路、欧拉回路的性质来做。有两种情况：一种是欧拉回路。全部房间的门的个数都是偶数个，而且此时初始房间不是0，此时存在要求的路径。假设初始是0则不行。还有一种是欧拉通路。仅仅有两个房间门是奇数个。剩下都是偶数个。而且这两个房间一个是0。一个是当前起点，而且起点不能是0，此时也存在要求的路径，否则不存在。

输入比較蛋疼

#include<cstring>

#include<string>

#include<fstream>

#include<iostream>

#include<iomanip>

#include<cstdio>

#include<cctype>

#include<algorithm>

#include<queue>

#include<map>

#include<set>

#include<vector>

#include<stack>

#include<ctime>

#include<cstdlib>

#include<functional>

#include<cmath>

using namespace std;

#define PI acos(-1.0)

#define MAXN 500100

#define eps 1e-7

#define INF 0x7FFFFFFF

#define LLINF 0x7FFFFFFFFFFFFFFF

#define seed 131

#define mod 1000000007

#define ll long long

#define ull unsigned ll

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

int in[30],out[30];

char s[20],s1[200];

int main(){

    int i,j;

    int m,n;

    int a,flag,ans,fk;

    while(scanf("%s",s)!=EOF){

        if(s[0]=='E'&&strlen(s)>5)  break;

        scanf("%d%d",&m,&n);

        getchar();

        ans = 0;

        flag = 0;

        fk = 0;

        memset(in,0,sizeof(in));

        for(i=0;i<n+1;i++){

            gets(s1);

            int p = 0;

            while(sscanf(s1+p,"%d",&a)==1){

                ans++;

                in[a]++;

                in[i]++;

                while(s1[p]!='\0'&&s1[p]!=' ')  p++;

                while(s1[p]!='\0'&&s1[p]==' ')  p++;

            }

        }

        for(i=0;i<n;i++){

            if(in[i]&1) flag++;

        }

        if(!flag){

            if(!m)  fk = 1;

            else    fk = 0;

        }

        else{

            if(flag==2&&m!=0&&in[m]&1&&in[0]&1)   fk = 1;

            else    fk = 0;

        }

        if(fk)  printf("YES %d\n",ans);

        else    puts("NO");

    }

    return 0;

}

秒客网

POJ--1300--Door Man【推断无向图欧拉通路】

相关文章