定义
欧拉路径是经过图中每条边恰好一次的路径，欧拉回路是经过图中每条边恰好一次的回路。
结论：（半）欧拉图判定：
- （弱）连通；
- 度数奇偶性。
欧拉回路要求所有点的度数是偶数，路径则允许两个节点有奇度数。
适用性 / 套路
就是一些常见套路和模型：
- ... 和 ... 相差 1。（超级常见）
然后转换成：
- 给边定向。
求解：Hierholzer 算法
在判定一个图具有欧拉回路后，进行该算法。
算法基于 dfs，每次搜索到一条边就标记，同时标记反向边（如有），并在该节点的邻接表中删除该边，保证复杂度是 \(O(|E|+|V|)\)。
vector 存图实现：
此时 vector 里需要保存当前边的编号。每次取出从 vector::back() 取出，然后 vector::pop_back()。
vector<pair<int, int>> e[E];
int stk[E], siz;
bool vis[E];
int tot, cur = 0;
void dfs(int u){while(!e[u].empty()){pair<int, int> edge = e[u].back();e[u].pop_back();int v = edge.first;if(vis[edge.second]) continue;vis[edge.second] = 1;dfs(v);stk[++siz] = edge.second;}
}
链式前向星实现
相较之下，链式前向星需要的修改极少。
只需要在遍历边时，int &i = head[u]，即引用 head[u]，自动修改，实现删边。
记得 tot 初始为 1，实现 e ^ 1 求 e 的反边。
int head[N];
int to[E], nxt[E];
int tot = 1;
bool vis_e[M];
void add(int u, int v, int id){to[++tot] = v;nxt[tot] = head[u];eid[tot] = id;head[u] = tot;deg[v]++;
}
void dfs2(int u){for(int &i = head[u]; i; i = nxt[i]){if(vis_e[i]) continue;int v = to[i];vis_e[i] = vis_e[i ^ 1] = 1;int tmp = eid[i];dfs2(v);ans[++ans_cnt] = tmp;}
}
例题
Luogu P11762 走亲访友
因为最后要求删边成一颗树，我们正难则反，考虑先找到这个树。
随便 dfs 出一颗生成树。
路径是陌生的，但回路是熟悉的。——MagicDark（赵海鲲）
可以考虑将限制变紧：要求起点和终点相同。
因为不在生成树上的边只能走一次，联想到欧拉回路（另一种解释）。
那么需要构造使得回路方案对应路径方案，即让每个点的度数为偶数。
-
当前点已经偶度数，不管。
-
当前点奇度数，复制它和父亲的连边，相当于要求走两遍。可以证明一定可以成功构造。
这样生成树的边只会至多经过两次，非生成树的变只会至多经过一次，路径长度至多为 \(n + m - 1 \leq k\)。（数据范围）
CodeForces 547D
网格图的套路，建模可以连接一个点的横纵坐标。
于是转换为给每条边定向，事实上很多欧拉回路题都是转换成定向。两种方向对应颜色。
那么发现相差 1，这又是一个欧拉回路题的常见点——相差 1，因为不差就太简单了。
相差 1，出现奇度点，还是考虑怎么搞成偶数。新建超级源点 \(0\)，连向所有奇度点即可。
\(O(n)\) 欧拉回路。
Luogu P9731 Balance
这种 2 的幂不好搞怎么办，一般先去看 2 的情况怎么做。然后可以分治思想。
\(S = 2\)
此时，就是给两个数定顺序，就是给边定向了。
又是差 1，又是一个源点连向奇度点。
感觉这种题挺套路的。
\(S = 2 ^ k, k \gt 1\)
