ACM3018欧拉回路

欧拉回路

欧拉回路：图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+];

     degree=new int[g+];

     odd=new int[g+];

     vis=new int[g+];

     record=new int[g+];

     cnt=;

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

     {

         p[i]=-;

         degree[i]=;

         odd[i]=;

         vis[i]=;

     }

 }

 void destroy()

 {

     delete []p;

     delete []degree;

     delete []odd;

     delete []vis;

     delete []record;

 }

 int find(int x)

 {

     if(p[x]<)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)==)

     {

         init(n);

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

         {

             scanf("%d %d",&a,&b);

             degree[a]++;

             degree[b]++;

             Union(a,b);

         }

         int f;

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

         {

             f=find(i);

             if(!vis[f])

             {

                 vis[f]=;

                 record[cnt++]=f;

             }

             if(degree[i]%==)

             odd[f]++;

         }

         int res=;

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

         {

             if(degree[record[i]]==)continue;

             if(odd[record[i]]==)

             res++;

             else res+=odd[record[i]]/;

         }

         destroy();

         printf("%d\n",res);

     }

     return ;

 }