P1636 Einstein学画画

一笔画问题

P1636 Einstein学画画

如果一个图存在一笔画，则一笔画的路径叫做欧拉路，如果最后又回到起点，那这个路径叫做欧拉回路。

奇点：跟这个点相邻的边数目有奇数个的点

不存在奇数个奇点的图

PS： 对于有一笔画的图，存在以下两个定理：

定理一：存在欧拉路的条件：图是连通的，有且只有2个奇点

定理二：存在欧拉回路的条件：图是连通的，有0个奇点

so，如果寻找欧拉回路，对任意一个点进行深度优先遍历

如果寻找欧拉路，则对一个奇点进行深度优先遍历

时间复杂度O（m+n），m为边数，n为点数

代码：

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

using namespace std;

int n,m,x,y,maq=,ans=;

int a[];

int main()

{

    cin>>n>>m;

    for(int i=;i<=m;i++)

    {

        cin>>x>>y;

        a[x]++;a[y]++;

        if(x>maq)

        maq=x;

        if(y>maq)

        maq=y;

    }

    for(int i=;i<=maq;i++)

    if(a[i]%!=)

       ans++;           //计算有多少个奇点

    if(ans==||ans==)  //符合欧拉路或欧拉回路，一笔画

    {

        cout<<;

        return ;

    }

    cout<<ans/;         //两个奇点确定一笔画，多少组奇点确定多少组笔画

    return ;

}