定义
欧拉路径 / 欧拉路：一条路径，满足：通过所有边恰好一次，且每个点都被走到过。
欧拉回路：一条路径，满足：通过所有边恰好一次，且每个点都被走到过，终点和起点相同。
欧拉图：存在欧拉回路的图。
半欧拉图：存在欧拉路径的图。
判定
有向图欧拉回路
一个有向图是欧拉图，当且仅当：
- 图是强连通的。
- 每个点的出度等于入度。
有向图欧拉路径
一个有向图是半欧拉图，当且仅当：
- 图是弱联通的。（把有向边改成无向边后，图是连通的）
- 恰好存在一个点 $S$，其出度比入度多一；恰好存在一个点 $T$，其入度比出度多一。
- 除 $S$ 和 $T$ 外，其他点的出度等于入度。
无向图欧拉回路
一个无向图是欧拉图，当且仅当：
- 图是连通的。
- 每个点度数均为偶数。
无向图欧拉路径
一个无向图是半欧拉图，当且仅当：
- 图是连通的。
- 恰有 $0$ 个或 $2$ 个度数为奇数的顶点。（$0$ 个时有欧拉回路，否则 $2$ 个奇度点为起点和终点）
寻找
利用 Hierholzer 算法。
Hierholzer 算法
首先，用上面的判定方法，判断是否存在欧拉路径或欧拉回路，并确定起点。
之后，从起点 $S$ 开始进行 DFS，每次走过一条边就把边删掉。
过程中，如果一个点的边被删完了，就将其加入答案栈。
最终，从栈顶按顺序输出答案栈中的元素即可。
伪代码
$$
\begin{array}{ll}
1 & \textbf{Input. } \text{The edges of the graph } e , \text{ where each element in } e \text{ is } (u, v) \\
2 & \textbf{Output. } \text{The vertex of the Euler Road of the input graph}.\\
3 & \textbf{Method. } \\
4 & \textbf{Function } \text{Hierholzer } (u) \\
5 & \qquad \textbf{for } \text{each Edge} e \text{ Begin with } u\\
6 & \qquad\qquad \textbf{delete } e \text{ from E}\\
7 & \qquad\qquad \text{Hierholzer }(v) \\
8 & \qquad\textbf{Insert } v \text{ into stack}\\
9 & \textbf{Endfunction}\\
10& \textbf{Print } \text{stack in Reverse order}.
\end{array}
$$
\begin{array}{ll}
1 & \textbf{Input. } \text{The edges of the graph } e , \text{ where each element in } e \text{ is } (u, v) \\
2 & \textbf{Output. } \text{The vertex of the Euler Road of the input graph}.\\
3 & \textbf{Method. } \\
4 & \textbf{Function } \text{Hierholzer } (u) \\
5 & \qquad \textbf{for } \text{each Edge} e \text{ Begin with } u\\
6 & \qquad\qquad \textbf{delete } e \text{ from E}\\
7 & \qquad\qquad \text{Hierholzer }(v) \\
8 & \qquad\textbf{Insert } v \text{ into stack}\\
9 & \textbf{Endfunction}\\
10& \textbf{Print } \text{stack in Reverse order}.
\end{array}
$$
P7771 【模板】欧拉路径
给定有向图，保证其弱联通，求字典序最小的欧拉路径。
对每个点的出边按字典序排序，跑 $\textbf{Hierholzer}$ 即可。
代码用优先队列实现了排序这一过程。
const int MAXN = 1e5 + 10, MAXM = 2e5 + 10;
int n, m;
priority_queue<int, vector<int>, greater<int> > e[MAXN];
int oud[MAXN], ind[MAXN];
vector<int> path;
void Hierholzer(int x) {
while(!e[x].empty()) {
int v = e[x].top(); e[x].pop();
Hierholzer(v);
}
path.push_back(x);
}
int main() {
n = read(); m = read();
for(int i = 1; i <= m; i++) {
int u = read(), v = read();
e[u].push(v);
ind[v]++; oud[u]++;
}
int ok = 1, S = 0, T = 0;
for(int i = 1; i <= n; i++) {
if(oud[i] - ind[i] == 1) {
if(S) ok = 0;
else S = i;
} else if(ind[i] - oud[i] == 1) {
if(T) ok = 0;
else T = i;
} else if(ind[i] != oud[i]) ok = 0;
}
if(!ok) printf("No\n");
else if((S == 0 && T != 0) || (S != 0 && T == 0)) printf("NO\n");
else {
if(S == 0) S = 1; //此时S==0&&T==0，有欧拉回路，随便定起点
Hierholzer(S);
for(int i = path.size() - 1; i >= 0; i--) printf("%d ", path[i]);
putchar('\n');
}
return 0;
}