由于在有向图中Hierholzer 算法不需要删除反向边因此我们可以使用其它更加方便的数据结构来保存图。例如我们可以使用邻接表^8保存有向边得到有向图 Hierholzer 算法的另一种 C 代码实现。// e[i] 是一个类型为 vectorint 的变量保存了节点 i 与哪些节点之间有边相连 // ans 是一个类型为 vectorvectorint 的变量用来存储我们找到的回路 // 回路用边的形式表示一条边用有两个元素的 vectorint 表示 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; vectorint 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; }
有向图Hierholzer算法的另一种实现
由于在有向图中Hierholzer 算法不需要删除反向边因此我们可以使用其它更加方便的数据结构来保存图。例如我们可以使用邻接表^8保存有向边得到有向图 Hierholzer 算法的另一种 C 代码实现。// e[i] 是一个类型为 vectorint 的变量保存了节点 i 与哪些节点之间有边相连 // ans 是一个类型为 vectorvectorint 的变量用来存储我们找到的回路 // 回路用边的形式表示一条边用有两个元素的 vectorint 表示 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; vectorint 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; }
