本讲定位：图论系列正篇的最后一讲。回到图论的起点——1736 年欧拉解决哥尼斯堡七桥问题，用的就是本讲这套判定。它的判定条件简单到可以口算（数一数有几个奇度点），但实现有三个能让你 0 分的坑，而且都不是”写慢了”而是”写错了”。本讲做了九组实测，四个数字值得先记住：朴素 DFS 边走边输出在随机图上输出非法路径的比例随边数从 7.24% 涨到 15.74%；有向图上 Hierholzer 忘记倒序，79.40% 直接非法；连通性检查把孤立点也算进去，在含孤立点的数据上错 81.84%；不写当前弧优化，两点间 2 万条重边的图上慢 1597.2 倍（$6\times10^8$ 次扫描 vs $4\times10^4$ 次）。另有两条正面结论各经数万组验证零反例：判定条件对无向图和有向图都是充要的；邻接表按终点升序排好后跑 Hierholzer，产出的就是字典序最小的欧拉路径。文中所有代码经
g++ -O2 -std=c++14 -Wall编译运行，并与”枚举所有边的走法”的暴力搜索对拍。前置知识：第 01 讲（链式前向星的成对边编号
i^1——本讲终于用上了当初埋的伏笔）、第 02 讲（DFS 与递归爆栈）、第 09 讲（并查集，用来判连通，也可以用 DFS 代替）。不需要第 13～15 讲。适合对象：第 2、3 节标 J⭐（判定条件是 CSP-J 选择题级别的常识）；第 4～7 节标 S；第 8 节（哈密顿路）标 S⭐⭐，只需知道结论。
P2731 [USACO3.3] 骑马修栅栏：$m$ 条栅栏（边），每条连接两个栅栏结点（点编号 $1 \sim 500$）。要求每条栅栏恰好走一次，输出经过的结点序列；有多解输出字典序最小的。保证有解。
“每条边恰好走一次”就是欧拉路径。这类题的诱人写法是：
void dfs(int u) {
printf("%d\n", u); // 走到哪输出到哪
for (size_t i = 0; i < g[u].size(); i++) {
int v = g[u][i].first, id = g[u][i].second;
if (!used[id]) { used[id] = 1; dfs(v); }
}
}
看起来天经地义，但它是错的。错在哪、错多少，第 5.1 节用实测回答。
| 欧拉路径 / 回路 | 哈密顿路径 / 回路 | |
|---|---|---|
| 要求 | 每条边恰好经过一次 | 每个点恰好经过一次 |
| 判定 | $O(n+m)$，数奇度点 | NP 完全 |
| 构造 | $O(n+m)$，Hierholzer | 指数级 |
只差”边”和”点”一个字，一个是送分题，一个是世界难题。 读题时务必看清。
术语：
允许重复经过点，这是它和哈密顿路的根本区别。