P7771 【模板】欧拉路径

· · 题解

P7771 【模板】欧拉路径。

摘自学习笔记 初级图论 第六章。

建议在博客内阅读。

6.1 定义与判定

做题时基本用不到上述定义（大雾）。

不严谨地说，欧拉图能够从任意一点作为起点一笔画完整张图然后回到该点，而半欧拉图只能从某两个点 S,T 开始才能画完整张图，其中 S,T 分别作为起点和终点。

欧拉图的判定：一张无向图 G 是欧拉图，当且仅当 G 是连通图且每个顶点的 度数都是偶数。一张有向图 G 是欧拉图，当且仅当 G 是 SCC 且每个顶点的入度和出度相等。

考虑证明上述结论。

无论是对于无向图还是有向图而言，必要性都是显然的。考虑最终欧拉回路的形态，每次进入一个点，都要从该点走出去，所以出边和入边必须两两抵消。对于起始点，它一开始走出去的边和最后走回它的边同样抵消了，所以有向图存在欧拉回路必须满足每个点出度和入度相等。同理可证无向图每个点的度数必须为偶数。

充分性通过构造法证明。考虑无向图，首先找到图上任何一个回路 P（不需要是欧拉回路）。因为除掉所有孤立点，每个点的度数都 \geq 2，所以回路必然存在。然后从图上删去 P 的所有边，并删去所有孤立点。形成的所有子图仍然满足每个点的度数均为偶数，因为 P 中每个点的度数为 2。由于每个子图均与 P 有交点，所以只需要将子图的欧拉回路接到 P 上即可得到原图的欧拉回路。因此我们对子图进行同样的操作。边的个数有穷，所以整个过程必然结束，继而我们得到原图的欧拉回路。同理可证有向图欧拉回路判定条件的充分性。

半欧拉图的判定：一张无向图 G 是半欧拉图，当且仅当 G 存在两个奇度数顶点。一张有向图 G 是半欧拉图，当且仅当 G 弱连通，恰存在一个顶点使得出度减入度等于 1，恰存在一个顶点使得入度减出度等于 1，且剩余所有顶点出入度相等。弱连通定义为将所有有向边替换为无向边后，整张图连通。

6.2 求欧拉路径：Hierholzer 算法

Hierholzer 算法的核心是不断往当前回路的某个点中插入环，这和欧拉回路存在的判定条件的充分性证明如出一辙，或者说完全等价。

先考虑有向图吧，因为有向图不需要考虑重边的问题。

6.2.1 朴素方法

根据流程，我们有一个朴素的实现方法：首先 dfs 找到经过某个点的任意一个环 P（不需要是简单环），将 P 上的所有边标记为已删去。然后依次加入 P 上的每个节点 p_1, p_2, \cdots, p_{|P|}, p_1。加入 p_i 之前，我们先递归找到 p_i 所在子图（我们删去了一些边）的欧拉回路，然后插入当前路径。因此这是一个递归形式的算法。

每次枚举到一个点时，我们都要遍历它的所有出边以找到第一个没有被删去的边，复杂度为 \mathcal{O}(m ^ 2)。

若用双向链表维护每个点剩余的所有出边，则每条边只会被遍历一次，时间复杂度 \mathcal{O}(n + m)。

进一步地，我们发现每次删去的环边一定是每个节点所有没有被删去的出边中开头的若干个。也就是说，如果给 u 的所有出边 (u, v_i) 钦定一个遍历顺序 (u, v_1), \cdots, (u, v_{out(u)})，那么找环时被删去的一定是开头的若干条边 (u, v_1), (u, v_2), \cdots, (u, v_k)。因为我们不会因找不到环而反悔掉走某一条边的操作。

不断无脑深搜，最终一定能找到环。

证明该结论。不妨设我们从 u 开始找环，每次走当前节点第一条没有被删去的出边并删去。走到节点 v \neq u 时，设这是我们第 i 次进入 v，那么我们只会离开 v 共 i - 1 次（每次离开必然对应一次进入，而在第 i 次进入之前，只有 i - 1 次进入）。故此时我们只删掉了 v 的 i - 1 条出边，而 v 有不少于 i 条出边：第 i 次进入 v 意味着 in(v) \geq i，而 in(v) = out(v) 所以 out(v) \geq i。因此我们必然能从 v 走出去到别的节点。

因此，最终必然只可能在 u 处走不到其它节点。但这意味着我们已经找到了一个环。

根据上述结论，我们不需要维护双向链表了。存图用的链式前向星可以满足我们的要求，因为我们每次只会删去开头的出边。这样改进后，链表头就和网络最大流 Dinic 算法的当前弧非常相似，都是 记录第一个有用的边 以省去一条条跳无用边的时间。

该结论同时也证明了找到一个环的复杂度关于环上边数线性，所以总复杂度即 \mathcal{O}(n + m)。

注意，需要使用双向链表维护将一个环插入当前回路的过程，否则复杂度会退化成 \mathcal{O}(n(n +m))（如果一旦走到目标节点而非目标节点不可以在往外走时就认为找到环，复杂度会退化成 \mathcal{O}(m(n + m))）。因为这样处理一个环的复杂度变成了所有未处理的边的个数之和。

6.2.2 巧妙方法

上述做法的时间复杂度已经足够优秀，但实现起来稍微有些复杂。我们希望算法能够更简单。

我们可以用自己的语言描述复杂的方法干了些什么，再思考有哪些地方可以简化。

从整体上考察，我们无非就是实现了这样的步骤：从一个起点开始找到一个环，然后以环上的每个起点开始找到一个环 …… 不断递归下去。

然后思考究竟是哪里麻烦了。我们会发现，为了依次从环上的每个起点开始找环，我们需要先 显式 地将这个环找到，排出来，再依次处理上面的所有节点。所以我们需要一个 dfs 函数找环，另一个递归式函数解决欧拉回路问题。

这样太蠢了，因为无论以怎样的顺序安排环上节点的找环顺序，都不会影响欧拉回路的正确性。我们只是找环并插入啊，换个顺序又不会让问题变得无解。

因此，我们直接在 dfs 找环的回溯过程中，直接对环上的每个节点找环。换句话说，我们将原来找环的顺序倒过来，这样我们就没有必要先显式地找到当前环了，而是在回溯的过程中，一边对当前点找环，一边往回路中插入当前环。

综上，我们得到了求解欧拉回路的最常用算法 —— Hierholzer 算法的具体步骤：遍历当前节点 u 的所有出边 (u,v)，若 (u,v) 未走过，那么向节点 v 深搜。遍历完所有出边后，将 u 加入路径。最终得到的就是一条反着的欧拉路径。倒过来即可。

如果要求字典序最小，只需在一开始对每个点的所有出边从小到大排序。这样一来，欧拉回路上从左往右看，每个点的后继都取到了理论最小值。

6.2.3 无向图和欧拉通路

以上，我们通过两小节的篇幅提出并优化了有向图欧拉回路的求解方法。

对于无向图的欧拉回路，我们可以类似有向图欧拉回路一样做，唯一的注意点是我们需要对边判重。使用求桥边时的成对变换技巧，用 2k 和 2k + 1 存储一条边的两个方向，并开桶记录。不能只判返祖边，因为可能有重边。

对于无向图和有向图的欧拉通路，注意必须从奇点或唯一的出度大于入度的点开始 dfs。其它地方和欧拉回路没有区别。

模板题 P7771 【模板】欧拉路径 代码如下。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m, lar, top, stc[N], in[N], hd[N];
vector<int> e[N];
void dfs(int id) {
  for(int &i = hd[id]; i < e[id].size(); ) dfs(e[id][i++]);
  stc[++top] = id;
}
int main() {
  cin >> n >> m;
  for(int i = 1; i <= m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    e[u].push_back(v), in[v]++;
  }
  for(int i = 1; i <= n; i++) {
    sort(e[i].begin(), e[i].end());
    if(abs((int) e[i].size() - in[i]) > 1) puts("No"), exit(0);
    if(e[i].size() > in[i])
      if(lar) puts("No"), exit(0);
      else lar = i;
  }
  dfs(lar ? lar : 1);
  if(top != m + 1) puts("No");
  else {
    reverse(stc + 1, stc + top + 1);
    for(int i = 1; i <= top; i++) cout << stc[i] << " ";
  }
  return 0;
}

6.3 参考文章