python/TangDou/AcWing/EulerPath/HDU3018.cpp

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;

int n, m;
int p[N];   // 并查集的父亲数组
int d[N];   // 度
int odd[N]; // 奇数度节点个数

// 并查集
int find(int a) {
    if (a != p[a]) p[a] = find(p[a]);
    return p[a];
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("HDU3018.in", "r", stdin);
#endif
    while (~scanf("%d%d", &n, &m)) { // 多组测试数据
        // 并查集初始化
        for (int i = 1; i <= n; i++) p[i] = i;
        // 初始化度
        memset(d, 0, sizeof d);
        // 连通分量中奇数点的个数
        memset(odd, 0, sizeof odd);
        // m条边
        while (m--) {
            int a, b;
            scanf("%d%d", &a, &b);
            d[a]++, d[b]++;       // 维护度
            p[find(a)] = find(b); // 维护并查集
        }
        // 枚举每个节点
        for (int i = 1; i <= n; i++)
            odd[find(i)] += d[i] % 2; // 族长x身上记录了家族中所有节点奇数度的总个数

        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (find(i) == i) {          // 只统计族长
                if (d[i] == 0) continue; // 孤立的点，放过
                if (odd[i] == 0)         // 奇数度个数为0，则一笔画
                    cnt++;
                else
                    cnt += odd[i] / 2; // 否则是奇数点个数/2
            }
        }
        // 输出总的笔画数
        printf("%d\n", cnt);
    }
    return 0;
}