POJ 1300 Door Man 欧拉路的判断

水题，不过这里整理一下欧拉路的基本概念和判断方法。

欧拉路：G为连通无向图，经过G每条边一次并且仅有一次的路径成为欧拉路

欧拉回路：欧拉路的起点和终点为同一个点的路

具有欧拉回路的无向图G称为欧拉图

判定：

无向图的判定：顶点的度全为偶数或者有且只有两个为奇数的图有欧拉路。如果顶点全为偶数，则可以以任意点为起点并且最终会回到起点构成欧拉回路。如果顶点有两个点为奇数，则这两个点必定为起点和终点。

有向图的判定：顶点的出度和入度之差全部为0或者只有一个点为1，一个点为-1的图有欧拉路。如果全部为0则可以取任意点为起点并且最终会回到起点构成欧拉回路，否则则差为1的点为起点，-1的为终点。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
#include <string>
#include <iostream>
#include <map>
#include <cstdlib>
#include <list>
#include <set>
#include <queue>
#include <stack>
#include <sstream>

using namespace std;

typedef long long LL;
const int maxn = 105;
int deg[maxn],n,m;
string buf;

int main() {
    //freopen("/tmp/in.txt","r",stdin);
    while(cin >> buf) {
        int cntodd = 0,cntdoor = 0;
        if(buf == "ENDOFINPUT") break;
        memset(deg,0,sizeof(deg));
        cin >> n >> m;
        getline(cin,buf);
        for(int i = 0;i < m;i++) {
            getline(cin,buf);
            int tmp;
            stringstream sin(buf);
            while(sin >> tmp) {
                deg[i]++;
                deg[tmp]++;
                cntdoor++;
            }
        }
        cin >> buf;
        for(int i = 0;i <= m;i++) if(deg[i] & 1) cntodd++;
        if(cntodd == 0 && n == 0) cout << "YES " << cntdoor;
        else if(cntodd == 2 && n != 0 && deg[0] % 2 && deg[n] % 2) 
            cout << "YES " << cntdoor;
        else cout << "NO";
        cout << endl;
    }
    return 0;
}