本文主要是介绍欧拉回路求解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
先判断能不能形成欧拉回路 如果能那就输出欧拉回路路径
zoj 2238 poj 1780 Code
输出一个数字序列 使得n位的十进制数都在里面
递归的方法求解
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <string>#define eps 1e-8
#define op operator
#define MOD 10009
#define MAXN 1000100
#define INF 0x7fffffff
#define MEM(a,x) memset(a,x,sizeof a)
#define ll __int64using namespace std;int list[MAXN];
int s[MAXN];
char ans[MAXN];
int cnt,res;void dfs(int v,int m)
{
// cout<<"dfs"<<endl;int w;while(list[v]<10){w=v*10+list[v];list[v]++;s[cnt++]=w;v=w%m;}
}int main()
{
//freopen("ceshi.txt","r",stdin);int n;while(scanf("%d",&n)!=EOF){if(n==0) break;if(n==1){puts("0123456789");continue;}int m=(int)pow(10.0,(double)(n-1)); //m=10^(n-1)MEM(list,0);cnt=0; res=0;int v=0;dfs(v,m);
// cout<<"1111"<<endl;while(cnt){v=s[--cnt];ans[res++]=v%10+'0';v/=10;dfs(v,m);
// cout<<"222"<<endl;}
// cout<<"3333"<<endl;for(int i=1;i<n;i++)printf("0");while(res) printf("%c",ans[--res]);puts("");}return 0;
}
Fleury算法
能不走桥就不走桥
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <string>#define eps 1e-8
#define op operator
#define MOD 10009
#define MAXN 200
#define INF 0x7fffffff
#define MEM(a,x) memset(a,x,sizeof a)
#define ll __int64using namespace std;int n,m;//顶点个数
struct stack
{int top,node[MAXN];
};
stack s;
int edge[MAXN][MAXN];void dfs(int x)
{
// cout<<"xxxx "<<x<<endl;s.top++;s.node[s.top]=x;for(int 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)
{s.top=0; s.node[s.top]=x;while(s.top>=0){int b=0;for(int i=0;i<n;i++){if(edge[s.node[s.top]][i]>0){b=1; break;}}if(b==0){printf("%d ",s.node[s.top]+1);s.top--;}else{s.top--;dfs(s.node[s.top+1]);}}puts("");
}int main()
{
freopen("ceshi.txt","r",stdin);scanf("%d%d",&n,&m);MEM(edge,0);int s,e;for(int i=0;i<m;i++){scanf("%d%d",&s,&e);edge[s-1][e-1]=1; edge[e-1][s-1]=1;}//如果存在奇数度顶点 则从奇数度顶点出发 否则从顶点0出发int num=0,start=0;for(int i=0;i<n;i++){int d=0;for(int j=0;j<n;j++)d+=edge[i][j];//看有多少点与该点相连 如果奇数 就是奇数度if(d&1){start=i;num++;}}if(num==0||num==2) Fleury(start);else printf("No Eular path\n");return 0;
}
这篇关于欧拉回路求解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
