首页 > 代码库 > ACM3018欧拉回路

ACM3018欧拉回路

2024-07-14 13:08:35   225人阅读

欧拉回路

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

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

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

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

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

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

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

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

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

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

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

3.利用dfs输出路径。

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

 1 #include<iostream>  2 using namespace std; 3 int n,m,cnt; 4 int *p,*degree,*odd,*vis,*record; 5 void init(int g) 6 { 7     p=new int[g+1]; 8     degree=new int[g+1];  9     odd=new int[g+1];10     vis=new int[g+1];11     record=new int[g+1];12     cnt=0;13     for(int i=0;i<=g;i++)14     {15         p[i]=-1;16         degree[i]=0;17         odd[i]=0;18         vis[i]=0;19     }20 }21 void destroy()22 {23     delete []p;24     delete []degree;25     delete []odd;26     delete []vis;27     delete []record;28 }29 int find(int x)30 {31     if(p[x]<0)return x;32     return p[x]=find(p[x]);33 }34 void Union(int a,int b)35 {36     int fa=find(a);37     int fb=find(b);38     if(fa==fb)return;//这一步判断很重要，在这里错了好多次，其他地方没错；39     int da=p[fa];40     int db=p[fb];41     if(da>db)42     {43         p[fa]=fb;44         p[fb]+=da;45     }46     else47     {48         p[fb]=fa;49         p[fa]+=db;50     }51 }52 int main()53 {54     int a,b;55     while(scanf("%d %d",&n,&m)==2)56     {57         init(n);58         for(int i=1;i<=m;i++)59         {60             scanf("%d %d",&a,&b);61             degree[a]++;62             degree[b]++;63             Union(a,b);64         }65         int f;66         for(int i=1;i<=n;i++)67         {68             f=find(i);69             if(!vis[f])70             {71                 vis[f]=1;72                 record[cnt++]=f;73             }74             if(degree[i]%2==1)75             odd[f]++;76         }77         int res=0;78         for(int i=0;i<cnt;i++)79         {80             if(degree[record[i]]==0)continue;81             if(odd[record[i]]==0)82             res++;83             else res+=odd[record[i]]/2;84         }85         destroy();86         printf("%d\n",res);87     }88     return 0;89 }

 


联系
我们