题意:
给n个房间和m道门以及起点,问是否可以从起点到0号房间,经过每道门恰好一次。
分析:
把门看作边则是无向图是否存在欧拉路的问题。
代码:
//poj 1300
//sep9
#include <iostream>
using namespace std;
const int maxN=32;
char s[1024];
char tmp[20];
int start,n,cnt;
int d[maxN]; void solve()
{int i,num=0;for(i=0;i<n;++i) if(d[i]%2==1)++num;if((num==0&&start==0)||(num==2&&d[start]%2==1&&d[0]%2==1&&start!=0)){printf("YES %d\n",cnt); return ;}printf("NO\n"); return ;
}int main()
{while(1){gets(s);if(strcmp(s,"ENDOFINPUT")==0)break; else if(s[0]=='S'){memset(d,0,sizeof(d));cnt=0;sscanf(s,"%s%d%d",tmp,&start,&n);for(int i=0;i<n;++i){gets(s);int x,p=0,t;while(s[p]==' ') ++p;while(sscanf(s+p,"%d%n",&x,&t)==1){++d[i];++d[x];++cnt; p+=t;while(s[p]==' ') ++p;} }scanf("%*s");solve();}} return 0;
}