基础部分
概念：
- 欧拉回路：经过每条边恰好一次的回路（回到起点）。
- 欧拉通路：经过每条边恰好一次的通路（不回起点）。
- 欧拉图：具有欧拉回路的图。
- 半欧拉图：不具有欧拉回路，但具有欧拉通路的图。
- 有向图强连通：任意两个顶点都可以通过有向边相互到达。
- 有向图弱连通：将有向边换成无向边后，任意两个顶点连通。
性质：
- 欧拉图中所有顶点的度数都为偶数（不管有向无向）。
- 欧拉图为若干环的并，且每条边被包含在奇数个环中。
- 一张图中只会有偶数个奇度数点。
- 用边互不相交的路径覆盖一张图的边，所需的最少路径数为\(\frac{1}{2}count(奇度数点)\)。
考虑证明最后一个性质：
设有\(2n\)个奇度数点，将其分成两两一组，共\(n\)组。
每组中相互连边，则图中不存在奇度数点，可以用\(1\)条欧拉回路覆盖。
将欧拉回路中新连的边删去，就形成了\(n\)条路径，故\(ans\le n\)。
一条路径至多将两个奇度数点变成偶度数点（即\(2\)个端点），故\(ans\ge n\)。
综上，\(ans=n\)。
判定：
- 无向图是欧拉图当且仅当：非零度顶点连通且顶点的度数都为偶数。
- 无向图是半欧拉图当且仅当：非零度顶点连通且恰有两个奇度数顶点。
- 有向图是欧拉图当且仅当：非零度顶点强连通且每个顶点入度和出度相等。
- 有向图是半欧拉图当且仅当：非零度顶点弱连通且至多一个顶点入度与出度差\(1\)且至多一个顶点出度与入度差\(1\)且其他每个顶点入度和出度相等
求欧拉路板子：
使用Hierholzer算法。
其核心是不断向当前路中的一个点中加入环。
考虑朴素做法：每次找到一个环，删掉其中所有边，并对其中每个点找环插入到答案中。用链式前向星维护每个点第一条有用的边，时间复杂度\(O(n+m)\)。
复杂度已足够优秀，但是实现很麻烦。实际上朴素做法是将环显示地找到再做其他操作。而找环的顺序对答案是没有影响的，所以我们可以将找环的顺序倒过来，即不必显式地找到当前环，只需在回溯的过程中一边对当前点找环，一边向答案中插入当前环。由于顺序倒过来了，所以答案也倒过来了。
得到流程：
- 对于当前节点\(u\)，遍历其所有未走过的出边\((u,v)\)，对\(v\)深搜。
- 遍历完所有出边后，将当前节点\(u\)加入答案，最终得到的就是一条倒着的欧拉路。
要求字典序最小，对每个顶点的出边排序即可。
无向图中，要对边判重（一条边只能走正边或反边中的一条）。
板子
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int n,m,tot=0,s=0,tp=0,z=0,st[maxn],cur[maxn],head[maxn],ind[maxn];
vector<int> e[maxn];
inline void add(int u,int v){
e[u].push_back(v);
}
void dfs(int u){
for(int &i=cur[u];i<e[u].size();){
dfs(e[u][i++]);
}
st[++tp]=u;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1,u,v;i<=m;++i){
scanf("%d%d",&u,&v);
add(u,v);
ind[v]++;
}
for(int i=1;i<=n;++i){
sort(e[i].begin(),e[i].end());
if(abs((int)e[i].size()-ind[i])>1){
puts("No");
return 0;
}
if(e[i].size()>ind[i]){
if(s){
puts("No");
return 0;
}
else s=i;
}
}
dfs(s?s:1);
if(tp!=m+1){
puts("No");
return 0;
}
for(int i=tp;i>=1;--i){
printf("%d ",st[i]);
}
return 0;
}