给定一张无向图，若存在一条从节点
S
S
S到节点
T
T
T到路径，恰好不重不漏地经过每条边一次（可以重复经过途中的某个节点）。则称该路径为
S
S
S到
T
T
T的欧拉路。
特别地，若存在一条从节点
S
S
S出发的路径，恰好不重不漏地经过每条边一次（可以重复经过途中的某个节点），能够回到节点
S
S
S，则称该路径为欧拉回路。存在欧拉回路的图叫做欧拉图。
欧拉图的判定定理
一张无向图为欧拉图，当且仅当无向图连通并且每一个节点的度数（出入度之和）为偶数。
欧拉路的判定定理
一张无向图中存在欧拉路，当且仅当无向图连通，并且图中恰好有两个节点的度数为奇数，其他节点的度数都是偶数。那么这个图中就存在欧拉路，并且这两个度数为奇数的店就是欧拉路的起点
S
S
S和终点
T
T
T。
欧拉图的具体求法：
欧拉图每个节点度数为偶数说明：只要到达一个节点，就必定有一条尚未走过的边可以离开该点故在上面的伪代码中，调用
d
f
s
(
1
)
dfs(1)
dfs(1)，不断递归，每次都走从“从
x
x
x出发的第一条未访问的边”的另一端点
y
y
y，最终一定能回到节点
1
1
1，产生一条回路。
当然这条回路不能保证经过了图中的每条边，所以dfs函数会继续考虑从x出发的其他未访问的边，找到第二条回路。
我们需要把这些回路按适当的方法拼接在一起，形成整张图的欧拉回路。一个很显然的拼接方法是：把第二条回路嵌入第一条回路中间即可。
但是这个算法的时间复杂度是
O
(
N
M
)
O(NM)
O(NM)的，主要原因是一个点会被重复便利多次。即使这个店本身就已经被访问过了。
假设我们采用邻接表储存无向图，我们可以在访问一条边
(
x
,
y
)
(x,y)
(x,y)后，及时修改表头
f
i
r
s
t
[
x
]
first[x]
first[x]，令它指向吓一跳边。这样我们每次只需要去除
f
i
r
s
t
[
x
]
first[x]
first[x]，就自然跳过了所有已经访问的边。同时为了避免栈溢出，我们可以手动模拟栈，实现递归与非递归之间的转换，时间复杂度是
O
(
N
+
M
)
O(N+M)
O(N+M)。
参考代码：
#include<bits/stdc++.h>
#define in read()
#define MAXN 200050
#define MAXM MAXN<<1
#define re register
using namespace std;
const int N=100050;
int n,m,ans[N],t=0,deg[N];
int nex[MAXM],first[MAXN],to[MAXM],tot=1;
bool vis[N];
inline int read(){
int x=0,f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
return x*f;
}
inline void addedge(int u,int v){
deg[u]++,deg[v]++;
nex[++tot]=first[u];
first[u]=tot;
to[tot]=v;
}
stack<int>stk;
void euler(){
stk.push(1);
while(!stk.empty()){
int x=stk.top(),e=first[x];
while(e and vis[e])e=nex[e];
if(e){
int v=to[e];
stk.push(v);
vis[e]=vis[e^1]=true;
first[x]=nex[e];
}
else{
stk.pop();
ans[++t]=x;
}
}
}
int main(){
n=in,m=in;
for(re int i=1;i<=m;i++){
int u=in,v=in;
addedge(u,v);
addedge(v,u);
}
for(re int i=1;i<=n;i++)
if(deg[i]%2==1){cout<<"No"<<'\n';return 0;}
euler();
for(re int i=t;i;i--)
cout<<ans[i]<<" ";
return 0;
}
推荐练习：
1.P6066 [USACO05JAN]Watchcow