一、概念解释
欧拉路：给定无孤立结点图G，若存在一条路，经过图中每边一次且仅一次，该条路称为欧拉路。
欧拉路的存在条件：没有孤立结点，同时奇数度数的点只有2个或0个。
欧拉回路：若一个连通图中没有奇数度数的点，则该图中一定存在一条起点与终点重合的欧拉路，称为欧拉回路。
通俗地讲，欧拉路就是一笔画游戏，每条边只能走一次，问怎么画才能把所有边都画出来。欧拉回路就是在此基础上，不仅要把所有边都画出来，还要求起点和终点要是同一个地方。
二、判断欧拉路是否存在
要判断欧拉路是否存在，只需要判断奇数度数的个数即可。一般使用并查集来实现。代码如下：
//判断欧拉路是否存在
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#define INF 0x3f3f3f3f
#define mst(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1e5+5;
int pre[maxn];
int deg[maxn];
bool root[maxn];
void init()
{
for(int i=1;i<=10000;i++)
pre[i]=i;
}
int findr(int x)
{
if(pre[x]==x)
return x;
return pre[x]=findr(pre[x]);;
}
void mix(int x,int y)
{
int fx=findr(x);
int fy=findr(y);
if(fx!=fy)
pre[fy]=fx;
return ;
}
int main()
{
init();
int n,m;
cin>>n>>m;
mst(deg,0);mst(root,0);
for(int i=0;i<m;i++)
{
int a,b;
cin>>a>>b;
mix(a,b);
deg[a]++;deg[b]++;
}
int d=0;int cnt=0;
for(int i=1;i<=n;i++)
if(deg[i]&1)
d++; //奇数度数节点计数
for(int i=1;i<=n;i++)
root[findr(i)]=1;
for(int i=1;i<=n;i++)
if(root[i]) //判断是否有孤立节点
cnt++;
if(cnt==1&&(d==0||d==2))
cout<<"OK"<<endl;
else
cout<<"NO"<<endl;
return 0;
}三、Fleury算法求欧拉回路
要求欧拉回路，一般使用Fleury算法。这个算法的过程可以这样描述：
1、在原图中找一个任意路径L1(不需要是欧拉路)，并按照L1的顺序将L1上的点压入一个栈中
2、从L1的终点往回回溯，依次将每个点出栈。并检查当前点是否还有其他没有经过的边。若存在则以当前点为起点，查找L2，并对L2的节点同样用栈记录重复该算法。
3、当L1中的点全部出栈后，算法结束。(参考欧拉路·二)
具体代码实现如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <stack>
#define INF 0x3f3f3f3f
#define mst(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1e5+5;
int gra[1005][1005];
int deg[1005];
int path[maxn];
vector<int> g[1005];
int size;
int n;
void dfs(int u)
{
bool flag=1;
for(int i=0;i<g[u].size();i++)
{
int x=g[u][i];
if(gra[u][x]){
gra[u][x]--;
gra[x][u]--;
dfs(x);
}
}
path[size++]=u;
return ;
}
int main()
{
mst(path,0);size=0;
mst(gra,0);mst(deg,0);
int m;
cin>>n>>m;
for(int i=0;i<m;i++)
{
int u,v;
cin>>u>>v;
gra[u][v]++;gra[v][u]++;
deg[u]++;deg[v]++;
g[u].push_back(v);g[v].push_back(u);
}
int d=0;int st=1;
for(int i=1;i<=n;i++)
if(deg[i]&1){
d++;
st=i;
}
dfs(st);
for(int i=0;i<size;i++)
{
if(i==0)
cout<<path[i];
else
cout<<" "<<path[i];
}
cout<<'\n';
return 0;
}