题目描述

Einstein 学起了画画。

此人比较懒~~，他希望用最少的笔画画出一张画……

给定一个无向图，包含 nn 个顶点（编号 1 \sim n1∼n），mm 条边，求最少用多少笔可以画出图中所有的边。

样例

输入
5 5
2 3
2 4
2 5
3 4
4 5

输出
1

根据题意可得：无向图，一条边不会被描述多次
所以就可得出运用欧拉路的知识
通过统计每个点的出度和入度，来判断奇点的个数

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt[1005],ans;
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d %d",&x,&y);
        cnt[x]++;
        cnt[y]++;
    }
    for(int i=1;i<=n;i++){
        if(cnt[i]&1==1)
            ans++;
    }
    if(ans==0)
        puts("1");
    else
        printf("%d\n",ans/2);
    return 0;
}