佛洛莱算法输出欧拉回路。
#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <set> #include <iomanip> #include <algorithm> #define maxn 10010 #define INF 0xfffffff using namespace std; struct Stack { int top,node[maxn]; }s; int edge[maxn][maxn];//邻接矩阵 int n;//顶点个数 void dfs(int x) { int i; ++s.top; s.node[s.top]=x; for(i=0;i<n;++i) if(edge[i][x]>0) { edge[i][x]=0;//删除该边 edge[x][i]=0; dfs(i); break; } } void Fleury(int x) { int i,b; s.top=0;//入栈 s.node[s.top]=x; while(s.top>=0) { b=0; for(i=0;i<n;++i) if(edge[s.node[s.top]][i]>0) { b=1; break; } if(b==0)//如果没有点可以扩展，输出并出栈 { cout<<s.node[s.top]+1<<" "; --s.top; } else { --s.top; dfs(s.node[s.top+1]);//如果有点可以扩展 } } cout<<endl; } int main() { int i,j; int m,s,t;//边数、读入边的起点终点 int degree,num,start;//每个顶点的度、奇度顶点个数、欧拉回路的起点 cin>>n>>m; memset(edge,0,sizeof(edge)); for(i=0;i<m;++i) { cin>>s>>t; edge[s-1][t-1]=1;edge[t-1][s-1]=1; } //如果存在奇度顶点，则从奇度顶点出发，否则从顶点0出发 num=0;start=0; for(i=0;i<n;++i)//判断是否存在欧拉回路 { degree=0; for(j=0;j<n;++j) degree+=edge[i][j]; if(degree%2==1) { start=i;++num; } } if(num==0||num==2) Fleury(start); else cout<<"No Euler path"<<endl; return 0; } /* 9 14 1 2 1 8 2 3 2 8 2 9 3 4 4 5 4 6 4 9 5 6 6 7 6 9 7 8 8 9 */
