核心概述
单节点用于判定与构造无向/有向图的欧拉路径/欧拉回路（给出顶点序列或判无解），输入为带全局边编号的邻接表，复杂度 O(V+E)，边界以本仓库实现为准。
原文引述
Description: Eulerian undirected/directed path/cycle algorithm. Input should be a vector of (dest, global edge index), where for undirected graphs, forward/backward edges have the same index. Time: O(V + E) ——摘自 kactl/content/graph/EulerWalk.h
展开阐述
-
定义与背景
- 欧拉路径：遍历每条边恰一次的路径；欧拉回路：起终点相同的欧拉路径。
- 本仓库实现 eulerWalk(gr, nedges, src) 返回“顶点序列”；若无可行走则返回空序列。
-
典型适用场景
- 竞赛中判断是否存在欧拉路径/回路，并在存在时输出一条具体走法（顶点序列）。
- 允许重边；无向图需为每条无向边存两条有向记录并共享同一“全局边编号”，以防重复使用。
-
接口/数据结构（保持与实现一致的术语）
- gr：vector<vector<pair<int,int>>>，每个元素为 (dest, edgeId)。
- nedges：全局边数（无向图为原始边数），用于开辟“是否已用”标记。
- src：起点（既用于路径，也可用于回路的起点）。
- 返回值：若成功，长度应为 nedges+1 的顶点序列；否则为空。
-
核心流程与要点（Hierholzer 思路）
- 使用栈 s 从 src 出发深走；每条边仅当其 edgeId 尚未使用时才入栈并标记。
- 回退时将顶点压入 ret；最终返回逆序即为一条欧拉路径/回路。
- 邻接表要求携带 edgeId；无向图的两条方向边必须共享同一 edgeId。
-
判定条件（据本仓库压力测试 hasEulerWalk）
- 连通性（忽略孤立点）：将所有含边的顶点用并查集联通后应只在一个连通块内；起点若无边且图有边则无解。
- 无向图：
- 除起点外，每个顶点的“非自环出边数”需为偶数；若要求回路，则起点也需偶数。
- 有向图：
- 回路：每个顶点入度等于出度。
- 路径：所有顶点满足 |in−out|≤1；起点不得是入度大于出度的点；不存在超过 1 的差值。
-
复杂度与边界条件
- 时间 O(V+E)，空间与图存储同阶。
- 支持重边与自环（实现按 edgeId 去重，自环计入度差与连通性时按代码处理）。
- 若 ret.size() ≠ nedges+1 或存在负计数（实现中的 D 检查），应判为无解。
-
变体/扩展
- 欧拉路径 vs 欧拉回路：回路是路径的特例；可通过是否对起点做 D[src]++ 等开关实现两种模式。
- 有向/无向的统一：只要度数条件与连通性满足，核心构造流程一致。
- 多解：通常存在多条可行解，基于邻接顺序输出其中一条。
-
正确性要点与不变式
- 不变式：每条边最多被使用一次（由 eu[edgeId] 保证）；栈回退保证形成一段闭合的子回路；拼接过程中总边数严格匹配 nedges。
- 终止时 ret 的逆序覆盖所有边，且首尾为起点（回路时）或满足路径起止点条件。
-
与相邻技术对比及取舍
- 与 077-图论-强连通分量：SCC 关注点可达性分解与环检测，欧拉问题关注“边使用一次”的度数与连通性条件，适用面不同。
- 与 078-图论-拓扑排序：拓扑序仅适用于 DAG；欧拉路径/回路可存在于含环图，与 DAG 场景无交集。