欧拉图 & 欧拉路
定义
图中经过所有边恰好一次的路径叫欧拉路径（也就是一笔画）。如果此路径的起点和终点相同，则称其为一条欧拉回路。
- 欧拉回路：通过图中每条边恰好一次的回路。
- 欧拉通路：通过图中每条边恰好一次的通路。
- 欧拉图：具有欧拉回路的图。
- 半欧拉图：具有欧拉通路但不具有欧拉回路的图。
性质
欧拉图中所有顶点的度数都是偶数。
若 \(G\) 是欧拉图，则它为若干个环的并，且每条边被包含在奇数个环内。
判别法
- 无向图是欧拉图当且仅当：
- 非零度顶点是连通的。
- 顶点的度数都是偶数。
- 无向图是半欧拉图当且仅当：
- 非零度顶点是连通的。
- 恰有 2 个奇度顶点。
- 有向图是欧拉图当且仅当：
- 非零度顶点是强连通的。
- 每个顶点的入度和出度相等。
- 有向图是半欧拉图当且仅当：
- 非零度顶点是弱连通的
- 至多一个顶点的出度与入度之差为 1。
- 至多一个顶点的入度与出度之差为 1。
- 其他顶点的入度和出度相等。
当然，一副图有欧拉路径，还必须满足将它的有向边视为无向边后它是连通的（不考虑度为 \(0\) 的孤立点），连通性的判断我们可以使用并查集或 dfs 等。
存在欧拉回路（即满足存在欧拉回路的条件），也一定存在欧拉路径。
求欧拉路径或欧拉回路
寻找欧拉路径（默认存在）：
首先根据题意以及判定先确定起点 \(S\)。
从起点 \(S\) 开始 dfs 。
dfs 伪代码如下：
void dfs(int now){
枚举 now 的出边。
如果该边还未被访问
标记为已访问
dfs(该边连向的另一个点)
now入栈
}
最后倒序输出栈内的所有节点即可。
感性理解倒序输出的原因：如果是欧拉回路，那么遍历到哪，输出到哪也是对的，因为不管怎么走都会绕某个环走回起点，所以不到最后不会出栈，然而欧拉路径会出现边都被走过了，走不回起点，最后会停留在终点，遇到这种情况这种路径会最先出栈，于是只要把这个路径先走了，前面就和欧拉回路一样随便走就行，不会出栈，于是倒序输出就是对的。
例题
洛谷 P7771 【模板】欧拉路径
题目描述
求有向图字典序最小的欧拉路径。
输入格式
第一行两个整数 \(n,m\) 表示有向图的点数和边数。
接下来 \(m\) 行每行两个整数 \(u,v\) 表示存在一条 \(u\to v\) 的有向边。
输出格式
如果不存在欧拉路径，输出一行
No。否则输出一行 \(m+1\) 个数字，表示字典序最小的欧拉路径。
题意：给定 \(n\) 个点，\(m\) 条边，求这副有向图字典序最小的欧拉路径。
思路：
本题需要判断并找出有向图的欧拉路径。
由于本题保证“将有向边视为无向边后图连通”，所以判定时不用判断连通性。
还有一点要注意的是本题需要按照字典序输出。
这一点如何解决呢？
法一：
直接使用数组存邻接矩阵，枚举点 \(x\) 出边时，直接枚举编号从 \(1\) 到 \(n\) 的点 \(y\)，再判断 \(x\)，\(y\) 之间是否有未访问边，这样就解决了字典序的问题。
dfs 代码（对应伪代码）:
void dfs(int now){
for(int i = 1 ; i <= n ; i ++)
if(G[u][i] > 0)
G[u][i]--,dfs(i);
st.push(now);
}
但是这样的做法时间复杂度为 \(O(n^2)\)，显然会超时。
法二：
既然邻接矩阵不行，那我们就用时间复杂度更优的邻接表，将 \(now\) 的所有出边排序即可。链式前向星对于排序出边的操作有些困难，而 vector 则容易得多，所以选用 vector。
sort 代码：
for(int i = 1 ; i <= n ; i ++)sort(G[i].begin(), G[i].end());
dfs 代码：
void dfs(int now){
for(int i = a[now] ; i < g[now].size() ; i = a[now])
a[now] = i + 1,dfs(g[now][i]);
s.push(now);
}
//其中 a[now] 表示 G[now][1,2……,a[now] - 1] 都已经被标记访问过，下一次要从 G[now][a[now]] 开始访问。
dfs 时间复杂度：\(O(n)\)。
sort 时间复杂度：\(O(m\log m)\)。
总时间复杂度：\(O(n+m\log m)\)。
足以 AC 本题。
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#define MAXN 100005
using namespace std;
int n, m, u, v;
int cnt1, cnt2, tmp = 1;
int a[MAXN], rd[MAXN], cd[MAXN];
bool flag = true;
stack <int> s;
vector <int> g[MAXN];
int read(){
int t = 1, x = 0;char ch = getchar();
while(!isdigit(ch)){if(ch == '-')t = -1;ch = getchar();}
while(isdigit(ch)){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * t;
}
void write(int x){
if(x < 0){putchar('-');x = -x;}
if(x >= 10)write(x / 10);
putchar(x % 10 ^ 48);
}
void dfs(int now){
for(int i = a[now] ; i < g[now].size() ; i = a[now])
a[now] = i + 1,dfs(g[now][i]);
s.push(now);
}
int main(){
n = read();m = read();
for(int i = 1 ; i <= m ; i ++){
u = read();v = read();
g[u].push_back(v);
cd[u]++;rd[v]++;
}
for(int i = 1 ; i <= n ; i ++)sort(g[i].begin(), g[i].end());
for(int i = 1 ; i <= n ; i ++){
if(cd[i] != rd[i])flag = false;
if(rd[i] - cd[i] == 1)cnt1++;
if(cd[i] - rd[i] == 1)
cnt2++,tmp = i;
}
if(flag == false)
if(cnt1 != cnt2 || cnt1 != 1){
puts("No");return 0;
}
dfs(tmp);
while(!s.empty())
write(s.top()),putchar(' '),s.pop();
return 0;
}