欧拉回路（一笔画）
欧拉回路是图论中的一个经典概念，指一条经过图中每条边恰好一次并且起点和终点相同的闭合路径。通俗地讲，就是一笔画问题中能够不重复地走完所有边并回到起点的画法。
基本定义
欧拉回路：经过图中每条边恰好一次且闭合的回路。
欧拉通路：经过每条边恰好一次但不闭合的路径（起点和终点不同）。
欧拉图：具有欧拉回路的图称为欧拉图。
判定定理
无向图
一个连通无向图存在欧拉回路当且仅当图中所有顶点的度数均为偶数。
一个连通无向图存在欧拉通路（不闭合）当且仅当图中恰好有 0 个或 2 个奇度数顶点。若有 2 个，则它们分别为起点和终点。
有向图
一个有向图存在欧拉回路当且仅当图是强连通的（或忽略方向后连通，且各顶点在同一个弱连通分量中），并且每个顶点的入度等于出度。
一个有向图存在欧拉通路当且仅当最多只有一个顶点的出度 - 入度 = 1（起点），最多一个顶点的入度 - 出度 = 1（终点），其余顶点入度等于出度，且图是弱连通的。
常见算法
Hierholzer 算法（推荐，O(E)）
从起点开始深度优先搜索。
沿着边走，每走一条边就将其删除（或标记已用）。
当当前节点没有未使用的边时，将该节点压入栈中，并回溯。
最后将栈逆序输出，即得到欧拉回路/通路。
核心代码（无向图示例）：
cpp
vector<int> path; void dfs(int u) { while (!graph[u].empty()) { int v = graph[u].top(); // 取一条边 graph[u].pop(); // 删除该边 dfs(v); } path.push_back(u); // 后序记录 } // 最后 reverse(path.begin(), path.end()) 得到正确顺序Fleury 算法
每次选择桥边之前需要判断是否破坏图的连通性，效率较低（O(E²)），一般不推荐。
应用场景
邮路问题（中国邮递员问题）：在带权图中寻找最短闭合路径覆盖所有边。
DNA 片段拼接：将 DNA 片段视为边，重叠部分视为节点，寻找欧拉路径完成拼接。
电路布线、言语路径等。
示例验证
无向图：正方形四个顶点（每个顶点度数为 2），存在欧拉回路，如 A→B→C→D→A。
有向图：下图是否存在欧拉回路？
A→B, B→C, C→A, A→C
度数检查：A(出2入1), B(出1入1), C(出1入1) → 入度≠出度 → 无欧拉回路，但存在欧拉通路（从 A 到 C）。
例题
332. 重新安排行程 - 力扣（LeetCode）正是求有向图的欧拉通路（起点固定为 "JFK"），并要求字典序最小。使用 Hierholzer 算法 + 优先队列（或 multiset）即可高效解决。