精妙的深度优先搜索
虽然 Hierholzer 算法的流程看起来较为复杂，但我们可以通过一段精妙的代码，将算法流程中的两个步骤合并到同一个深度优先搜索过程中。
在图论的代码实现中，一条无向边一般会被拆成两条有向边。由于 Hierholzer 算法的流程需要我们删除一条无向边，因此我们需要同时删除一条有向边和它的反向边。这样的操作只有利用链式前向星^6（亦称边表）存储无向图时才能在 的时间复杂度内完成，因此下文的代码实现中，均使用链式前向星存储无向图。
Hierholzer 算法的一个 C++ 实现如下。请注意，为了便于分析与讲解，下面给出的代码实现并不是欧拉回路的最优时间复杂度实现。下文中，我们将提出该实现的一个优化。
// 为了方便存储一条边的众多信息，我们定义一个结构体 // // struct Edge { // int fn, nxt; // bool del; // }; // // 其中： // * fn 表示这条有向边的终点 // * nxt 表示链式前向星中，该有向边的后续边的编号，如果没有后续边则值为 0 // * del 表示这条边是否被遍历过了 // // e[] 是一个类型为 Edge 的数组，e[i] 表示链式前向星中编号为 i 的边 // p[] 是一个类型为 int 的数组，p[i] 表示以 i 为起点的第一条边在链式前向星中的编号 // 如果没有以 i 为起点的有向边则 p[i] 的值为 0 // // 为了方便我们查找某一条有向边的反向边，当我们向链式前向星中加入第 i（i 从 1 到 m）条无向边 x - y 时， // 我们会将有向边 x -> y 存储在 e[i * 2]，有向边 y -> x 存储在 e[i * 2 + 1]， // 这样，e[i] 和 e[i ^ 1] 就互为反向边 // // ans 是一个类型为 vector<Edge> 的变量，用来存储我们找到的回路 void dfs(int sn) { for (int i = p[sn]; i != 0; i = e[i].nxt) { // 这条边已经被遍历过了，跳过 if (e[i].del) continue; // 删除有向边 e[i] 和它的反向边 e[i ^ 1] e[i].del = e[i ^ 1].del = true; // 继续遍历相邻点 dfs(e[i].fn); // 将边 e[i] 加入结果序列中 ans.push_back(e[i]); } }调用dfs(S)后，ans里就保存了从节点S出发，并回到节点S的欧拉回路。需要注意的是，此时ans中保存的欧拉回路，是我们求出的欧拉回路的倒序。因此，我们还需要调用reverse(ans.begin(), ans.end())将ans中所有元素顺序倒转后，才能得到我们想要的欧拉回路。
