欧拉回路算法

raincity · 2025-12-16 11:51:25 · 算法·理论

本文为旧文重置版。

本文尝试还原求解欧拉回路的线性算法的推导动机。

算法流程

本节推导的是无向图的欧拉回路算法。有向图的欧拉回路算法与无向图基本一致。

首先，观察到孤点与欧拉回路无关，可以认为图中没有孤点，或 n = 1。

考虑重述“G 有欧拉回路“的判定条件。

考虑分析欧拉图 G 的性质。显然 G 连通。并且，因为欧拉回路访问每个点 u 时都会先走一条边到达 u，再走一条边离开 u，所以 u 的度数是偶数。

考虑证明满足以上条件的 G 都是欧拉图。因为 G 连通，假设 G 上不存在环，则 G 是一棵树，树的叶子节点度数为 1，与每个点的度数是偶数矛盾。所以 G 上存在环 C。考虑从图 G 中删除环 C 的边集，得到图 G'。则 G' 每个点的度数也是偶数，且每个连通块至少包含一个环 C 上的点。考虑递归求出每个连通块的欧拉回路，再用环 C 把各回路串起来，就能得到整张图的欧拉回路。

考虑重述“G 有 s \rightsquigarrow t 的欧拉路径“的判定条件。这里的路径实际上指的是途径（walk），但是既然 OI 界俗称欧拉回路，我也不方便改了。

不难发现 G 有 s \rightsquigarrow t 的欧拉路径，当且仅当给 G 添加一条边 (u, v) 得到的图 G' 有欧拉回路。

至此，我们已经得到了求解欧拉回路/路径的多项式时间的算法。

考虑直接设计一个求欧拉路径的算法，这样的算法也能求出欧拉回路。

如果 G 有欧拉回路，则任取起点 s = t。否则 s, t 分别是图上唯二的度数是奇数的点。

考虑子问题-分治-倍增-递归。任取 s 的一条出边 s \to u。一个直接的想法是递归到求删除边 (s, u) 后得到的图 G' 从 u 出发的欧拉路径，但是很遗憾，新图虽然满足点的度数的奇偶性的限制，却不一定连通。

考虑如何处理这个问题。如果图 G' 真的不连通，则 G' 一定只有两个连通块，且分别包含 s 和 u。一个关键的观察是，t 一定属于 u 所在的连通块。

引理：欧拉图 G 一定是边双连通图。考虑上文构造欧拉回路的过程不难得证。

所以，如果 s = t（求欧拉回路），则 G' 是边双连通图，删除一条边后得到的图 G' 一定连通。如果 s \neq t（求欧拉路径），则给 G 增加边 (s, t) 后得到的图 G'' 是边双连通图，假设 t 属于 s 所在的连通块，则 (s, u) 是 G'' 的割边，矛盾。所以 t 属于 u 所在的连通块。

所以，在这种情况下，可以先递归求出 s 所在的连通块中，s \rightsquigarrow s 的欧拉回路，再经过 s \to u 的边，最后递归求出 u 所在的连通块中，u \rightsquigarrow t 的欧拉路径。

这样我们就得到了一个 \mathcal O((n + m)^2) 的算法，瓶颈在于判定删除边 (s, u) 后图是否连通。

考虑进一步优化。考虑不要判定图是否连通。我们直接设 \operatorname{euler}(s) 返回 s 所在连通块中，以 s 开头的欧拉路径，并删除 s 所在连通块的所有边。先删除边 (s, u)，再递归调用 \operatorname{euler}(u)，最后递归调用 \operatorname{euler}(s)，就省去了判定连通性的步骤。我们只需要支持往欧拉回路的开头插入一个点（或者说一条边），这是容易的。时间复杂度 \mathcal O(n + m)。

代码实现

模板题：[UOJ 117] 欧拉回路。

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define sz(x) (int)(x).size()
using ll = long long;

const int kn = 1e5 + 10, km = 4e5 + 10;
int sid, n, m, d[kn];
vector<pair<int, int>> adj[kn];
vector<int> ans;

namespace undir {
bool vis[km];

void euler(int u) {
  while (sz(adj[u])) {
    auto [v, id] = adj[u].back();
    adj[u].pop_back();
    if (vis[id]) continue;
    vis[id ^ 1] = true;
    euler(v);
    ans.push_back(id % 2 == 0 ? id / 2 : -(id / 2));
  }
}

void solve() {
  rep (i, 1, m) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back({v, 2 * i});
    adj[v].push_back({u, 2 * i + 1});
    ++d[u], ++d[v];
  }
  rep (i, 1, n)
    if (d[i] % 2 == 1) {
      cout << "NO\n";
      exit(0);
    }
  int s = 1;
  while (s <= n && !sz(adj[s])) ++s;
  euler(s);
}
}  // namespace undir

namespace dir {
void euler(int u) {
  while (sz(adj[u])) {
    auto [v, id] = adj[u].back();
    adj[u].pop_back();
    euler(v);
    ans.push_back(id);
  }
}

void solve() {
  rep (i, 1, m) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back({v, i});
    ++d[u], --d[v];
  }
  rep (i, 1, n)
    if (d[i]) {
      cout << "NO\n";
      exit(0);
    }
  int s = 1;
  while (s <= n && !sz(adj[s])) ++s;
  euler(s);
}
}  // namespace dir

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> sid >> n >> m;
  if (sid == 1) undir::solve();
  else dir::solve();
  if (sz(ans) < m) {
    cout << "NO\n";
    return 0;
  }
  cout << "YES\n";
  for (int i = sz(ans) - 1; i >= 0; --i) cout << ans[i] << " \n"[i == 0];
}