HDU-1878 欧拉回路（连通性+偶数度数检验）

Problem Description

欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个图，问是否存在欧拉回路？

Input

测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是节点数N ( 1 < N < 1000 )和边数M；随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个节点的编号（节点从1到N编号）。当N为0时输入结束。

Output

每个测试用例的输出占一行，若欧拉回路存在则输出1，否则输出0。

Sample Input

3 3
1 2
1 3
2 3
3 2
1 2
2 3
0

Sample Output

1
0

---

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#include <climits>

using namespace std;

int vertexNum, edgeNum;
vector<vector<int>> grid(1005, vector<int>(1005, 0));
vector<bool> visit(1005, false);
vector<int> degree(1005, 0);

void DFS(int pos)
{
    visit[pos] = true;
    for (int i = 1; i <= vertexNum; ++i) {
        if (!visit[i] && grid[pos][i]) DFS(i);
    }
}

bool connect_check()
{
    int cnt = 0;
    for (int i = 1; i <= vertexNum; ++i) {
        if (!visit[i]) {
            DFS(i);
            ++cnt;
        }
    }

    return cnt == 1;
}

bool degeree_check()
{
    for (int i = 1; i <= vertexNum; ++i) {
        if (degree[i] & 1) return false;
    }

    return true;
}


int EulerCircuit()
{
    return (connect_check() && degeree_check()) ? 1 : 0;
}

void init()
{
    fill(degree.begin() + 1, degree.begin() + 1 + vertexNum, 0);
    fill(visit.begin() + 1, visit.begin() + 1 + vertexNum, false);
    for (int i = 1; i <= vertexNum; ++i) 
        fill(grid[i].begin() + 1, grid[i].begin() + 1 + vertexNum, 0);
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    while ((cin >> vertexNum) && vertexNum) {
        cin >> edgeNum;
        int from, to;
        for (int i = 0; i < edgeNum; ++i) {
            cin >> from >> to;
            grid[from][to] = grid[to][from] = 1;
            ++degree[from], ++degree[to];
        }
        cout << EulerCircuit() << endl;
        init();
    }

    return 0;
}

连通性检查和图中无奇点，两项检查都通过则存在欧拉回路。