1.亿些小定义
欧拉回路：通过图中每条边恰好一次的回路
欧拉通路：通过图中每条边恰好一次的通路
欧拉图：具有欧拉回路的图
半欧拉图：具有欧拉通路但不具有欧拉回路的图
还是比较好理解的，就是这个半欧拉图有点奇特，之前没有听说过。
2.性质
性质1：欧拉图中所有顶点的度数都是偶数。
证明：一条边增加的总度数为 $2$ ，奇数的乘积为奇数，所以没有可能。
性质2：若 $G$ 是欧拉图，则它为 若干个环的并，且 每条边被包含在奇数个环内。
证明：反证法： 假设有一条边属于偶数个环的并，那么必然会产生 奇度数点对，所以不能构成欧拉图。
性质3：设 $G$ 为弱连通有向图。$G$ 是欧拉有向图，当且仅当 $G$ 所有结点的出度等于入度。
其他性质不大看得懂 应该也没什么用，给出地址方便以后查看把：Link
3.正题：求欧拉回路或欧拉路
- Fleury 算法（避桥法）
算法流程为每次选择下一条边的时候优先选择不是桥的边。
最简单的实现方法是每次删除一条边之后暴力跑一遍 Tarjan 找桥，时间复杂度是 $\Theta(m(n+m))=\Theta(m^2)$。复杂的实现方法要用到动态图等，实用价值不高。
我的评价：既不如第二种好写，还没有第二种优，纯属 nt 算法，跳过。
- Hierholzer 算法
也称逐步插入回路法。
算法流程为从一条回路开始，每次任取一条目前回路中的点，将其替换为一条简单回路，以此寻找到一条欧拉回路。如果从路开始的话，就可以寻找到一条欧拉路。
暴力实现时间复杂度约为 $O(nm+m^2)$。跳过，直接看优化。
- Hierholzer 算法 with 当前弧优化
这才是绝杀算法。
将找回路的 DFS 和 Hierholzer 算法的递归合并，边找回路边使用 Hierholzer 算法，即可大大优化复杂度。
如果需要输出字典序最小的欧拉路或欧拉回路的话，因为需要将边排序，时间复杂度是 $\Theta(n+m\log m)$（计数排序或者基数排序可以优化至 $\Theta(n+m)$）。如果不需要排序，时间复杂度是 $\Theta(n+m)$。
看懂了吗？直接上例题！
例题
简化题意：
给定一张有 500 个顶点的无向图，求这张图的一条欧拉路或欧拉回路。如果有多组解，输出最小的那一组。
在本题中，欧拉路或欧拉回路不需要经过所有顶点。
边的数量 $m$ 满足 $1\leq m \leq 1024$。
代码：（包含Hierholzer 算法 with 当前弧优化）
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
return s*w;
}
const int N=505;
struct node{
int to;
bool exists;
int r;
friend bool operator < (const node &a,const node &b){return a.to<b.to;};
};
int cnt[N],deg[N],reft[N],m,start;
vector<node> e[N];
stack<int> ans;
void heir(int x)
{
for(int &i=cnt[x];i<e[x].size();)
{
if(e[x][i].exists)
{
auto b=e[x][i];e[x][i].exists=0;
e[b.to][b.r].exists=0;
i++;
heir(b.to);
}
else i++;
}
ans.push(x);
}
int main()
{
m=read();
for(int i=1,a,b;i<=m;i++)
{
a=read(),b=read();
e[a].push_back((node){b,1,0}),e[b].push_back((node){a,1,0});
++deg[a],++deg[b];
}
for(int i=1;i<=N-5;i++) if(!e[i].empty()) sort(e[i].begin(),e[i].end());
for(int i=1;i<=N-5;i++) for(int j=0;j<e[i].size();j++) e[i][j].r=reft[e[i][j].to]++;
for(int i=1;i<=N-5;i++)
{
if(!deg[start]&°[i]) start=i;
else if(!(deg[start]&1)&&(deg[i]&1)) start=i;
}
heir(start);
while(!ans.empty()) printf("%d\n",ans.top()),ans.pop();
}