由于在有向图中，Hierholzer 算法不需要删除反向边，因此我们可以使用其它更加方便的数据结构来保存图。例如，我们可以使用邻接表^8保存有向边，得到有向图 Hierholzer 算法的另一种 C++ 代码实现。
// e[i] 是一个类型为 vector<int> 的变量，保存了节点 i 与哪些节点之间有边相连 // ans 是一个类型为 vector<vector<int>> 的变量，用来存储我们找到的回路 // 回路用边的形式表示，一条边用有两个元素的 vector<int> 表示 void dfs(int sn) { while (e[sn].size() > 0) { int fn = e[sn].back(); // 删除有向边 sn -> fn e[sn].pop_back(); // 继续遍历相邻点 dfs(fn); // 将边 sn -> fn 加入结果序列中 ans.push_back({sn, fn}); } }在上述实现中，我们每次遍历的是从 sn 出发，且未被删除的最后一条有向边 sn -> fn。之所以选择最后一条边，是因为我们可以通过 vector 的 pop_back 方法，在 的时间复杂度内删除这条边。因此上述实现的时间复杂度仍然是 的，且比链式前向星的实现方式更加简洁。
例题
我们仍然使用下面这道基础例题^7完整地展示 Hierholzer 算法在有向图中的使用。
直接使用当前弧优化的 Hierholzer 算法即可。本题的 C++ 代码如下。
#include <bits/stdc++.h> #define MAXN ((int) 1e5) #define MAXM ((int) 2e5) using namespace std; int n, m; vector<int> ans; struct Edge { // 因为不需要删除反向边，我们直接把编号为 idx 的边保存在 e[idx] 里 // 这样就不需要额外记一个 idx 了 int fn, nxt; bool del; } e[MAXM + 10]; int p[MAXN + 10]; int inDeg[MAXN + 10], outDeg[MAXN + 10]; // 加入第 idx 条有向边 x -> y void adde(int x, int y, int idx) { e[idx] = Edge { y, p[x], false }; p[x] = idx; } void dfs(int sn) { // 当前弧优化的 Hierholzer 算法 for (int i = p[sn]; i != 0; i = p[sn]) { if (e[i].del) { // 这条边已经被删除了，修改 p[sn] 指向它的下一条边 p[sn] = e[i].nxt; continue; } // 删除有向边 e[i]，不需要删除反向边 e[i].del = true; // 继续遍历相邻点 dfs(e[i].fn); // 将边 e[i] 的编号加入结果序列中 ans.push_back(i); } } int main() { // 读入点数和边数 scanf("%d%d", &n, &m); // 读入所有有向边 for (int i = 1; i <= m; i++) { int x, y; scanf("%d%d", &x, &y); adde(x, y, i); outDeg[x]++; inDeg[y]++; } // 检查是否所有点的入度等于出度 for (int i = 1; i <= n; i++) if (inDeg[i] != outDeg[i]) { printf("NO\n"); return 0; } // 必须从一个非零度节点开始深度优先搜索 for (int i = 1; i <= n; i++) if (inDeg[i] + outDeg[i] > 0) { dfs(i); break; } // ans 保存的是欧拉回路的倒序，必须 reverse 才是正确答案 reverse(ans.begin(), ans.end()); // 这里实际上是对原图弱连通性的检查 // 如果原图的非零度节点不连通，那么 ans 里将不足 m 条边 if (ans.size() != m) printf("NO\n"); else { // 输出欧拉回路 printf("YES\n"); for (int i = 0; i < m; i++) printf("%d%c", ans[i], "\n "[i + 1 < m]); } return 0; }
