欧拉回路

欧拉回路：图G，若存在一条路，经过G中每条边有且仅有一次，称这条路为欧拉路，如果存在一条回路经过G每条边有且仅有一次，

称这条回路为欧拉回路。具有欧拉回路的图成为欧拉图。

判断欧拉路是否存在的方法

有向图：图连通，有一个顶点出度大入度1，有一个顶点入度大出度1，其余都是出度=入度。

无向图：图连通，只有两个顶点是奇数度，其余都是偶数度的。

判断欧拉回路是否存在的方法

有向图：图连通，所有的顶点出度=入度。

无向图：图连通，所有顶点都是偶数度。

程序实现一般是如下过程：

1.利用并查集判断图是否连通，即判断可以作为起点的点的个数，如果大于1，说明不连通。

2.根据出度入度个数，判断是否满足要求。

3.利用dfs输出路径。

Notice:并查集使用中连接点时必须判断两点是否不在一个集合，不然可能会造成STACK_OVERFLOW的错误，下面做的这个就是血淋淋的例子啊！

#include<iostream> 
using namespace std;
int n,m,cnt;
int *p,*degree,*odd,*vis,*record;
void init(int g)
{
    p=new int[g+1];
    degree=new int[g+1]; 
    odd=new int[g+1];
    vis=new int[g+1];
    record=new int[g+1];
    cnt=0;
    for(int i=0;i<=g;i++)
    {
        p[i]=-1;
        degree[i]=0;
        odd[i]=0;
        vis[i]=0;
    }
}
void destroy()
{
    delete []p;
    delete []degree;
    delete []odd;
    delete []vis;
    delete []record;
}
int find(int x)
{
    if(p[x]<0)return x;
    return p[x]=find(p[x]);
}
void Union(int a,int b)
{
    int fa=find(a);
    int fb=find(b);
    if(fa==fb)return;//这一步判断很重要，在这里错了好多次，其他地方没错；
    int da=p[fa];
    int db=p[fb];
    if(da>db)
    {
        p[fa]=fb;
        p[fb]+=da;
    }
    else
    {
        p[fb]=fa;
        p[fa]+=db;
    }
}
int main()
{
    int a,b;
    while(scanf("%d %d",&n,&m)==2)
    {
        init(n);
        for(int i=1;i<=m;i++)
        {
            scanf("%d %d",&a,&b);
            degree[a]++;
            degree[b]++;
            Union(a,b);
        }
        int f;
        for(int i=1;i<=n;i++)
        {
            f=find(i);
            if(!vis[f])
            {
                vis[f]=1;
                record[cnt++]=f;
            }
            if(degree[i]%2==1)
            odd[f]++;
        }
        int res=0;
        for(int i=0;i<cnt;i++)
        {
            if(degree[record[i]]==0)continue;
            if(odd[record[i]]==0)
            res++;
            else res+=odd[record[i]]/2;
        }
        destroy();
        printf("%d\n",res);
    }
    return 0;
}