POJ1300 Door Man 歐拉回路的判斷

題目鏈接：

1300

題意：

一個房子中有(編號0~N-1)N個房間和X個連通兩個房間的門，所有房間都是連通的，每次經過一扇門時這扇門會被關閉。問：一個人從M號房間出發能否成功到達0號房間並關閉所有門。

題解：

此題是歐拉回路的入門題，首先學習無向圖歐拉回路的判斷定理：

無向圖G 存在歐拉通路的充要條件是：G 為連通圖，並且G 僅有兩個奇度結點（度數為奇數的頂點）或者無奇度結點。

該題是固定起點和終點的的無向圖。

所以能構成歐拉回路只有兩種情況：

1 所有點的度數為偶數

2 起點終點度數為奇數 其他均為偶數

代碼：

#include
#include
#include
using namespace std;
int main()
{
    int degree[30];
    int m,n,i,j,s,odd,even;
    char str[1005],str2[1005];
    while(scanf("%s",str)&&strcmp(str,"ENDOFINPUT")!=0)
    {
        s=odd=even=0;
        memset(degree,0,sizeof(degree));
        scanf("%d%d",&m,&n);
        getchar();
        for(i=0; i='0'&&str2[j]<='9')
                {
                    s++;
                    degree[i]++;
                    degree[str2[j]-'0']++;
                }
        }
        scanf("%s",str);
        for(i=0; i