题解 P1636 【Einstein学画画】

· · 题解

这不是图论，明明是数论！

我们先来了解一下一笔画的原理（欧拉一笔画原理）：

一个图形要能一笔画完成必须符合两个条件，

即图形是封闭联通的和图形中的奇点（与奇数条边相连的点）个数为0或2。

哥德堡七桥问题

本题依靠的是数学，如上面欧拉一笔画原理，一笔画要符合两个条件：

1、封闭联通：

本题并不需要理，因为没有连的点直接不管。

2、奇点个数为2或0：

本题的关键。如果奇点个数为0或2，就输出1.

不然，就输出奇点个数/2(因为我们可以把一个图分为多个图，直到奇点个数为0或2)。

附上代码：

#include<bits/stdc++.h>

using namespace std;
long long N,M,a,b,n[100005],ans;
int main()
{
    cin>>N>>M;
    for(int i=1;i<=M;i++)
    {
        cin>>a>>b;
        n[a]++;
        n[b]++; 
    }
    for(int i=1;i<=N;i++)
    {
        if(n[i]%2==1)ans++;
    }
    if(ans==0||ans==2)cout<<1<<endl;
    else
    {
        cout<<ans/2<<endl;
    }
    return 0;
}