题解 P1636 【Einstein学画画】

· · 题解

/* 这里用到一个定理，楼下说的已经很明白了，这里就复制以下OvO;

考察简单半欧拉图及其扩展定理，设顶点的度数为连接的边数,然后统计所有顶点中度数为奇数的顶点的个数n，则答案一定为n/2

用这个方法能过掉%90的点

第二个点是一个环，度为奇数的点为0个，但是好要一笔花完，这里就加一个特判，我第一次没加，就WA了好几次。。。

*/

#include<cstdio>
#include<iostream>
using namespace std;
int b[10001];
int main()
{
    int n,m,i,j,k,geshu=0,x,y;
    scanf("%d%d",&n,&m);
    for (i=1;i<=m;i++)//运用定理

{//运用定理 scanf("%d%d",&x,&y);//运用定理

    b[x]++;//运用定理

    b[y]++;//运用定理

}//运用定理

    for (i=1;i<=n;i++)
        if (b[i]%2==1)//判断度数
            geshu++;
    if (geshu)
        printf("%d",geshu/2);
    else//特判
        printf("%d",geshu+1);
}