假设数据输入时采用如下的格式进行输入：首先输入顶点个数n和边数m，然后输入每条边，每条边的数据占一行，格式为：u，v，表示从顶点u到顶点v的一条有向边
这里把欧拉回路的路径输出了出来：
手写栈：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 1005
int first[N],k,degree[N],visit[N];
struct stack{
int top,node[N];
}s;
struct Path{
int y,next,flag;
}path[N<<];
void add(int x,int y)
{
path[k].y=y,path[k].next=first[x],path[k].flag=k;
first[x]=k;
k++;
path[k].y=x,path[k].next=first[y],path[k].flag=k-;
first[y]=k;
k++;
}
void dfs(int u)
{
s.node[++s.top]=u;
for(int i=first[u];i!=-;i=path[i].next){
if(!visit[path[i].flag]){
visit[path[i].flag]=;
dfs(path[i].y);
break;
}
}
}
void Fleury(int x)
{
int b;
s.top=;
s.node[s.top]=x;
while(s.top>=){
b=;
int u=s.node[s.top];
for(int i=first[u];i!=-;i=path[i].next){
if(!visit[path[i].flag]){
b=;
break;
}
}
if(b==){//如果没有点可以扩展
printf("%d ",s.node[s.top]);
s.top--;
}
else{
s.top--;
dfs(s.node[s.top+]);
}
}
}
int main()
{
int n,m,u,v;
scanf("%d%d",&n,&m);
k=;
memset(first,-,sizeof(first));
memset(degree,,sizeof(degree));
memset(visit,,sizeof(visit));
for(int i=;i<m;i++){
scanf("%d%d",&u,&v);
add(u,v);
degree[u]++,degree[v]++;
}
int odd=,st=;
for(int i=;i<=n;i++){
if(degree[i]&) odd++,st=i;
}
if(odd==||odd==) {Fleury(st);}
else printf("No Euler path\n");
return ;
}
stl容器栈：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
#define N 1005
int first[N],k,degree[N],visit[N];
stack<int> s;
struct Path{
int y,next,flag;
}path[N<<];
void add(int x,int y)
{
path[k].y=y,path[k].next=first[x],path[k].flag=k;
first[x]=k;
k++;
path[k].y=x,path[k].next=first[y],path[k].flag=k-;
first[y]=k;
k++;
}
void dfs(int u)
{
s.push(u);
for(int i=first[u];i!=-;i=path[i].next){
if(!visit[path[i].flag]){
visit[path[i].flag]=;
dfs(path[i].y);
break;
}
}
}
void Fleury(int x)
{
int b;
s.push(x);
while(!s.empty()){
b=;
int u=s.top();
for(int i=first[u];i!=-;i=path[i].next){
if(!visit[path[i].flag]){
b=;
break;
}
}
if(b==){//如果没有点可以扩展
printf("%d ",s.top());
s.pop();
}
else{
s.pop();
dfs(u);
}
}
}
int main()
{
int n,m,u,v;
scanf("%d%d",&n,&m);
k=;
memset(first,-,sizeof(first));
memset(degree,,sizeof(degree));
memset(visit,,sizeof(visit));
for(int i=;i<m;i++){
scanf("%d%d",&u,&v);
add(u,v);
degree[u]++,degree[v]++;
}
int odd=,st=;
for(int i=;i<=n;i++){
if(degree[i]&) odd++,st=i;
}
if(odd==||odd==) {Fleury(st);}
else printf("No Euler path\n");
return ;
}
输入：
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
结果：
1 2 3 4 5 6 4 9 2 8 7 6 9 8 1