题解 | #欧拉回路# 度+并查集判断欧拉回路

//欧拉回路条件：1.结点度为偶数  2.连通分量为1
#include <iostream>
using namespace std;

const int N = 1010;

int n, m;
int p[N], d[N];

struct Edge{
    int from;
    int to;
};

Edge e[N];

int find(int x)
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

int main() {
    while(cin >> n >> m && n)
    {
        int a, b;
        bool sign  = true;   //判断是否有度为奇数的点

        for(int i = 1; i < N; i++) p[i] = i, d[i] = 0;

        for(int i = 0; i < m; i++)
        {
            scanf("%d %d", &a, &b);
            e[i].from = a;
            e[i].to = b;
            p[find(a)] = find(b);
            d[a]++;
            d[b]++;
        }

        if(n > m)   //边小于结点数，肯定为欧拉回路，直接排除
        {
            puts("0");
            continue;
        }
        
        for(int i = 1; i <= n; i++)
            if(d[i] % 2 == 1)
            {
                sign = false;
                break;
            }
        
        if(!sign)
        {
            puts("0");
            break;
        }

        int num = 0;
        for(int i = 1; i <= n; i++)   //所有非孤立节点是否只有一个连通分量
            if(p[i] == i && d[i] != 0) num++;
        
        if(num == 1) puts("1");
        else puts("0");
    }
}