POJ1300 Door Man 欧拉回路的判断

题目链接：

1300

题意：

一个房子中有(编号0~N-1)N个房间和X个连通两个房间的门，所有房间都是连通的，每次经过一扇门时这扇门会被关闭。问：一个人从M号房间出发能否成功到达0号房间并关闭所有门。

题解：

此题是欧拉回路的入门题，首先学习无向图欧拉回路的判断定理：

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

该题是固定起点和终点的的无向图。

所以能构成欧拉回路只有两种情况：

1 所有点的度数为偶数

2 起点终点度数为奇数 其他均为偶数

代码：

#include<iostream>#include<cstdio>#include<cstring>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<n; i++){gets(str2);for(j=0; j<strlen(str2); j++)if(str2[j]>='0'&&str2[j]<='9'){s++;degree[i]++;degree[str2[j]-'0']++;}}scanf("%s",str);for(i=0; i<n; i++){if(degree[i]%2==0)even++;elseodd++;}if((odd==0&&m==0)||(odd==2&&degree[m]%2==1&&degree[0]%2==1&&m!=0))cout<<"YES"<<' '<<s<<endl;elsecout<<"NO"<<endl;}return 0;}

伟人之所以伟大，是因为他与别人共处逆境时，