POJ 1300 - 阅读理解+恶心输入+欧拉回路

题意不太好理解....大致上: 是从某个指定的房间出发...问能否回到0房间...并且关掉图中所有的门..而门是关上后无法打开的...

输入比较奇葩..我是gets读入一行后再处理的...

再抽象一些...把门开作边..那么相当于找一条路径..使得便利所有的边..且每个边只遍历一次...这里分为两种情况..一种是从0出发..走完所有的边回到0...这是典型的欧拉回路...另一种是从其他点出发..到达0点..并且走完所有的边..

判断一个图能否存在欧拉回路..就是看所有点的度是否为偶数...因为所有的点必定都是进入多少次就要出去多少次...而只是一条路路径而非回路..那么起点和终点必须是奇数的度..而其他的点的度必须为偶数...

Program：

#include<iostream>#include<stdio.h>#include<algorithm>#include<string.h>#include<math.h>#include<map>#include<queue>#include<stack>#define ll long long#define oo 1000000000#define pi acos(-1)using namespace std;  int m,n,ans,a[105];char s[505];int main(){      int p,len,i,k;     while (~scanf("%s",s))     {           if (s[0]!='S') break;           scanf("%d%d",&m,&n);           gets(s);           memset(a,0,sizeof(a));           ans=0;           for (p=0;p<n;p++)           {                 gets(s);                 len=strlen(s);                 i=0;                 while (i<len)                 {                       k=0;                       while (s[i]>='0' && s[i]<='9')                       {                              k=k*10+s[i]-'0';                              i++;                         }                       if (k)                       {                              a[p]++;                              a[k]++;                              ans++;                                  k=0;                       }                       i++;                 }           }           gets(s);           k=0;           for (i=0;i<n;i++)              if (a[i]%2) k++;            if (!m)           {               if (!k)                   printf("YES %d\n",ans);                   else                   printf("NO\n");            }else           {               if (k==2 && a[m]%2 && a[0]%2)                   printf("YES %d\n",ans);                   else                   printf("NO\n");                           }     }     return 0;}