题解 P1636 【Einstein学画画】

九指客 · 2017-10-18 20:29:56 · 题解

特殊的一笔画问题

#include<bits/stdc++.h>//万能头文件；
using namespace std;
int a[2010];
int ans=0;
int main()
{
    int i,j,k,m,n,x,y;
    scanf("%d%d",&m,&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&x,&y);
        a[x]++;
        a[y]++;
    }
    for(i=1;i<=m;i++)
    {
        if(a[i]%2==1)//有奇数条路经过这个点；
        {
            ans++;
        }
    }
    if(ans)//必须没有或只有2个奇数点才能够一笔画，否则多一笔；
    printf("%d\n",ans/2);
    else //如果没有奇数点，可以一笔画；
    printf("1\n");
    return 0;
}