首页 > 代码库 > 欧拉回路总结
欧拉回路总结
一：一般欧拉回路的判定。
注意：判断欧拉回路之前要先判断图的连通性，只有满足图是连通的前提下，才进行以下判断。
无向图：统计每个点的度数，若图中没有度数为奇数的顶点，则存在欧拉回路，否则不存在。
有向图：统计每个点的初度和入度，若每个点的初度和入度都相等则存在欧拉回路，否则不存在。
二：一般欧拉通路的判定。
注意：判断欧拉通路之前要先判断图的连通性，只有满足图是连通的前提下，才进行以下判断。
无向图：统计每个点的度数，若图中没有度数为奇数的顶点或者度数为奇数的顶点只有两个，则存在欧拉通路，否则不存在。
有向图：统计每个点的初度和入度，若每个点的初度和入度都相等或者出了两个点之外的点入度和初度都相等，而这两个点中，一个点出度和入度之差为1，另一个之差是-1，则存在欧拉通路，否则不存在。
三：求解欧拉回路。
算法：无向图：在判断存在欧拉回路的前提下，用DFS搜索欧拉回路。随便选择一个点作为一个起点，然后访问与该点相邻的点，递归下去，如果没有邻接点，则回溯输出当前边。
1 //邻接表 2 void DFS(int u){ 3 for(int i=head[u];i!=-1;i=edge[i].next){ 4 if(!vis[edge[i].no]){ 5 vis[edge[i].no]=1;//注意在建图的时候，正向边和反向边的编号是相同的,vis数组来标记该边是否被访问 6 DFS(edge[i].v); 7 printf("%d %d\n",edge[i].v,u); 8 } 9 } 10 } 11 12 13 //临接矩阵 14 void DFS(int u){ 15 for(int i=1;i<=50;i++){ 16 if(mp[u][i]){ 17 mp[u][i]--; 18 mp[i][u]--; 19 DFS(i); 20 printf("%d %d\n",i,u); 21 } 22 } 23 }
有向图：还是DFS，但是此时记录路径的时候有所改变，要用一个数组先存起来，最后才输出。
1 void DFS(int u){ 2 for(int i=head[u];i!=-1;i=edge[i].next){ 3 if(!vis[edge[i].no]){ 4 vis[edge[i].no]=1;//注意在建图的时候，正向边和反向边的编号是相同的,vis数组来标记该边是否被访问 5 DFS(edge[i].v); 6 ans1[++top]=u;//ans1记录边的起点 7 ans2[top]=edge[i].v;//ans2记录边的终点 8 } 9 } 10 } 11 void print(){ 12 for(int i=top;i>=1;i--)//从后往前输出 13 printf("%d %d\n",ans1[i],ans2[i]); 14 }
四：求解欧拉通路。
算法：无向图：在判断存在欧拉通路的前提下，同上，用DFS，但是此时的的起点只能是度数为奇数的顶点。
有向图：同有向图欧拉回路，但是此时的起点是入度和初度之差为-1的点。
五：混合图的欧拉回路：
把该图的无向边随便定向，计算每个点的入度和出度。如果有某个点出入度之差为奇数，那么肯定不存在欧拉回路。因为欧拉回路要求每点入度 = 出度，也就是总度数为偶数，存在奇数度点必不能有欧拉回路。
现在每个点入度和出度之差均为偶数。将这个偶数除以 2，得 x。即是说，对于每一个点，只要将 x 条边反向（入>出就是变入，出>入就是变出），就能保证出 = 入。如果每个点都是出 = 入，那么很明显，该图就存在欧拉回路。
现在的问题就变成了：该改变哪些边，可以让每个点出 = 入？构造网络流模型。有向边不能改变方向，直接删掉。开始已定向的无向边，定的是什么向，就把网络构建成什么样，边长容量上限 1。另新建 s 和 t。对于入 > 出的点 u，连接边(u, t)、容量为 x，对于出 > 入的点 v，连接边(s, v)，容量为 x（注意对不同的点x不同）。之后，察看是否有满流的分配。有就是能有欧拉回路，没有就是没有。查看流值分配，将所有流量非 0（上限是 1，流值不是 0 就是1）的边反向，就能得到每点入度 = 出度的欧拉图。
由于是满流，所以每个入 > 出的点，都有 x 条边进来，将这些进来的边反向，OK，入 = 出了。对于出 > 入的点亦然。那么，没和 s、t 连接的点怎么办？和s 连接的条件是出 > 入，和 t 连接的条件是入 > 出，那么这个既没和 s 也没和 t 连接的点，自然早在开始就已经满足入 = 出了。那么在网络流过程中，这些点属于“中间点”。我们知道中间点流量不允许有累积的，这样，进去多少就出来多少，反向之后，自然仍保持平衡。
所以，就这样，混合图欧拉回路问题，解了。
六：题目：
uva10054:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=995&mosmsg=Submission+received+with+ID+13692247
题意：每个珠子两半有两种不同的颜色组成，相邻两珠子在接触的地方颜色相同，确认一些零碎的珠子，能否还原成完整的项链。
题解：每个珠子看成一条边的话，就是求是否存在欧拉回路，并且输出一种方案。这一题，要注意，如果不判连通性的话，也可以过，但是应该是要判连通性的，可能题目的数据不是很强。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<iostream> 5 using namespace std; 6 int mp[53][53]; 7 int deg[54]; 8 int n; 9 void init(){ 10 memset(mp,0,sizeof(mp)); 11 memset(deg,0,sizeof(deg)); 12 } 13 void DFS(int u){ 14 for(int i=1;i<=50;i++){ 15 if(mp[u][i]){ 16 mp[u][i]--; 17 mp[i][u]--; 18 DFS(i); 19 printf("%d %d\n",i,u); 20 } 21 } 22 } 23 bool flag; 24 int main(){ 25 int test,tt=1,u,v,start; 26 scanf("%d",&test); 27 while(test--){ 28 scanf("%d",&n); 29 flag=false; 30 init(); 31 for(int i=1;i<=n;i++){ 32 scanf("%d%d",&u,&v); 33 mp[u][v]++; 34 mp[v][u]++; 35 deg[u]++; 36 deg[v]++; 37 start=u; 38 } 39 for(int i=1;i<=50;i++){ 40 if(deg[i]%2==1){ 41 flag=true; 42 break; 43 } 44 } 45 if(tt>1)printf("\n"); 46 printf("Case #%d\n",tt++); 47 if(!flag)DFS(start); 48 else 49 printf("some beads may be lost\n"); 50 51 } 52 }
poj1637：http://poj.org/problem?id=1637
题意：混合图的欧拉回路
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 #include<queue> 6 #define INF 100000000 7 using namespace std; 8 const int MAXN=203; 9 int n,m; 10 int in[MAXN],out[MAXN]; 11 int u,v,d,total; 12 int pre[MAXN]; 13 struct Node{ 14 int c; 15 int f; 16 }; 17 Node mp[MAXN][MAXN]; 18 bool BFS(){ 19 memset(pre,0,sizeof(pre)); 20 pre[0]=1; 21 queue<int>Q; 22 Q.push(0); 23 while(!Q.empty()){ 24 int d=Q.front(); 25 Q.pop(); 26 for(int i=0;i<=n+1;i++){ 27 if(!pre[i]&&mp[d][i].c-mp[d][i].f){ 28 pre[i]=pre[d]+1; 29 Q.push(i); 30 } 31 } 32 } 33 return pre[n+1]>0; 34 } 35 int Dinic(int ps,int flow){ 36 int f=flow; 37 if(ps==n+1)return f; 38 for(int i=0;i<=n+1;i++){ 39 if(mp[ps][i].c-mp[ps][i].f&&pre[i]==pre[ps]+1){ 40 int a=mp[ps][i].c-mp[ps][i].f; 41 int t=Dinic(i,min(a,flow)); 42 mp[ps][i].f+=t; 43 mp[i][ps].f-=t; 44 flow-=t; 45 } 46 } 47 return f-flow; 48 } 49 int solve(){ 50 int sum=0; 51 while(BFS()) 52 sum+=Dinic(0,INF); 53 return sum; 54 } 55 void make(){ 56 total=0; 57 for(int i=1;i<=n;i++){ 58 if(in[i]<out[i]){ 59 mp[0][i].c+=(out[i]-in[i])/2; 60 } 61 else if(out[i]<in[i]){ 62 mp[i][n+1].c+=(in[i]-out[i])/2; 63 total+=(in[i]-out[i])/2; 64 } 65 } 66 } 67 int main(){ 68 int cas; 69 scanf("%d",&cas); 70 while(cas--){ 71 scanf("%d%d",&n,&m); 72 memset(mp,0,sizeof(mp)); 73 memset(out,0,sizeof(out)); 74 memset(in,0,sizeof(in)); 75 for(int i=1;i<=m;i++){ 76 scanf("%d%d%d",&u,&v,&d); 77 if(d==1){ 78 out[u]++; 79 in[v]++; 80 } 81 else{ 82 out[u]++; 83 in[v]++; 84 mp[u][v].c+=1; 85 } 86 } 87 bool flag=false; 88 for(int i=1;i<=n;i++){ 89 if(abs(in[i]-out[i])%2){ 90 flag=true; 91 break; 92 } 93 } 94 if(flag){ 95 printf("impossible\n"); 96 continue; 97 } 98 else{ 99 make(); 100 if(total==solve()) 101 printf("possible\n"); 102 else 103 printf("impossible\n"); 104 } 105 } 106 }