题解 | #欧拉回路#

#include <bits/stdc++.h>
#include <cstring>
#include <vector>
using namespace std;
int N, M;
int a, b;
int g[1001][1001];
void dfs(int v,vector<bool> &visited) {
    visited[v] = 1;
    for (int i = 1; i <= N; i++) {
        if (visited[i]==0&&g[v][i] == 1) {
            dfs(i,visited);
        }
    }
}
int main() {
    while (cin >> N && N) {
        cin >> M;
        memset(g, 0, sizeof(g));
        vector<int>degree(M + 1, 0);
        for (int i = 0; i < M; i++) {
            cin >> a >> b;
            if (a == b) continue;
            degree[a]++;
            degree[b]++;
            g[a][b] =g[b][a]= 1;
        }
        //判断连通与否
        bool can = 1;
        vector<bool> visited(N + 1, 0);
        dfs(1,visited);
        for (int i = 1; i <= N; i++) {
            //如果没被遍历，并且度数不为0，则不是孤立点，不存在欧拉回路
            if (visited[i] == 0 && degree[i] != 0) {
                cout << "0" << endl;
                can = 0;
                break;
            }
        }
        if (can == 1) {
            //判断度数是否都是偶数
            for (int i = 1; i <= N; i++) {
                //不是偶数，返回0
                if (degree[i] % 2 == 1) {
                    cout << "0" << endl;
                    can = 0;
                    break;
                }
            }
            if (can == 1) {
                cout << "1" << endl;
            }
        }
    }
}
// 64 位输出请用 printf("%lld")