网络上关于求欧拉回路的线性算法的资料普遍缺少证明。本文将通过分析欧拉回路的性质推导出这一算法。
算法流程
基本的定义可以参考 Alex_Wei 的博客，本文不再赘述。
算法流程部分仅推导求无向图欧拉回路的算法，求有向图欧拉回路的算法的推导过程是类似的，更改一些对应术语即可。
显然图中的孤立点与欧拉回路无关，本小节假设要么图中不存在孤立点，要么整张图就是一个孤立点。
性质 1：无向图 \(G\) 是欧拉图，当且仅当图 \(G\) 连通，且 \(\forall u \in G\)，\(2 \mid d(u)\)。
证明：必要性显然，下证充分性。
考虑归纳法。\(|E| = 0\) 时结论显然成立。假设 \(|E| < m\) 时结论成立，下证 \(|E| = m\) 时结论成立。
显然图中至少存在一个环（否则图将会是一棵树，树的叶子节点度数为 \(1\)，矛盾）。删除环上的边后图可能分裂成若干个连通块，但每个连通块中至少存在一个环上的点，并且仍然满足 \(\forall u \in G\)，\(2 \mid d(u)\)。由归纳假设，每个连通块都存在欧拉回路，用环把这些欧拉回路串起来即可得到原图的欧拉回路。
性质 2：若无向图 \(G\) 是欧拉图，则 \(G\) 是边双连通图。
证明：性质 1 的证明直接导出了这一结论。
性质 3：无向图 \(G\) 是半欧拉图，当且仅当图 \(G\) 连通，且 \(\sum_{u \in G} [2 \nmid d(u)] = 2\)。并且，设满足 \(2 \nmid d(u)\) 的两个点分别为 \(s, t\)，则 \(G\) 的欧拉迹的两个端点一定为 \(s, t\)。
证明：必要性显然，下证充分性。
在 \(s, t\) 之间再连一条边，则图会变成一张欧拉图。把新图的欧拉回路中 \((s, t)\) 这条边删掉即可得到原图的一条欧拉迹。
现在考虑构造一张欧拉图的欧拉回路或一张半欧拉图的欧拉迹。考虑递归构造，定义函数 \(dfs(s)\) 返回 \(s\) 所在的连通块的生成子图中一条 \(s \rightsquigarrow s\) 的欧拉回路或一条 \(s \rightsquigarrow t\) 的欧拉迹。
若整张图就是一个孤立点，则可以返回一条空途径 \(s\)。否则任取 \(s\) 的一条邻边 \((s, v)\) 并删除，有以下两种情况：
- 图变得不连通，则 \((s, v)\) 是原图的一条割边。由性质 2，我们要求的一定是一条欧拉迹。并且，\(t\) 一定在 \(v\) 所在的连通块，因为假设在原图加入 \((s, t)\) 这条边则原图会变得连通。因此可以返回 \(dfs(s) + dfs(v)\)。
- 图仍然连通。可以返回 \(s + dfs(v)\)。
这样我们就得到了一个 \(O(m (n + m))\) 的算法，瓶颈在于判断图是否连通。
我们希望避免判断图是否连通，即合并两种情况。实际上这是非常简单的。可以先调用 \(dfs(v)\)，设结果为 \(a\)，再调用 \(dfs(s)\)，设结果为 \(b\)，最后返回 \(b + a\)。这是因为如果图不连通，则 \(dfs(s)\) 和 \(dfs(v)\) 的过程互不干扰，否则 \(dfs(v)\) 时会把图删空，\(dfs(s)\) 会直接返回 \(s\)。
这样我们就得到了一个 \(O(n + m)\) 的算法，不过实现时有一些需要注意的地方：
- 删边可以用打标记 + 当前弧优化代替。
- \(dfs\) 并不需要真的返回一条途径，只需要不断向构造的途径里 prepend 新的点。这可以通过在 \(dfs\) 过程中执行 append，最后执行一次 reverse 解决。
- 不断 \(dfs(s)\) 其实很蠢，这相当于枚举 \(s\) 的每条出边并执行 \(dfs(v)\)，回溯前再 append \(s\)。
这样就得到了我们平时实现的算法。
参考实现
模板题：UOJ117 欧拉回路。本题要求输出边的顺序，只需要把回溯前 append \(s\) 这一步改成每次调用 \(dfs(v)\) 之后 append \((s, v)\) 这条边即可。
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#define len(x) int((x).size())
using ll = long long;
using db = long double;
template <typename T>
inline bool ckmin(T &x, const T &y) {
return y < x and (x = y, true);
}
template <typename T>
inline bool ckmax(T &x, const T &y) {
return x < y and (x = y, true);
}
int n, m;
namespace undirected {
constexpr int N = 1e5 + 5, M = 4e5 + 5;
int tot = 1, hd[N], nxt[M], to[M], d[N];
bool vis[M];
vector<int> p;
void ae(int u, int v) {
++d[u], ++d[v];
nxt[++tot] = hd[u], hd[u] = tot, to[tot] = v;
nxt[++tot] = hd[v], hd[v] = tot, to[tot] = u;
}
void dfs(int u) {
for (int &i = hd[u]; i > 0; i = nxt[i]) {
if (vis[i / 2]) {
continue;
}
vis[i / 2] = true;
int tmp = i % 2 == 1 ? -(i / 2) : i / 2;
dfs(to[i]);
p.push_back(tmp);
}
}
void proc() {
for (int i = 1; i <= m; ++i) {
int u, v;
cin >> u >> v;
ae(u, v);
}
int s = 0;
for (int i = 1; i <= n; ++i) {
if (d[i] % 2 == 1) {
cout << "NO\n";
return;
}
if (d[i] > 0) {
s = i;
}
}
if (s != 0) {
dfs(s);
}
if (len(p) < m) {
cout << "NO\n";
return;
}
cout << "YES\n";
for (int i = m; --i >= 0;) {
cout << p[i] << " \n"[i == 0];
}
}
}
namespace directed {
constexpr int N = 1e5 + 5, M = 2e5 + 5;
int tot, hd[N], nxt[M], to[M], inD[N], outD[N];
vector<int> p;
void ae(int u, int v) {
++inD[v], ++outD[u];
nxt[++tot] = hd[u], hd[u] = tot, to[tot] = v;
}
void dfs(int u) {
int &i = hd[u];
while (i > 0) {
int tmp = i;
i = nxt[i];
dfs(to[tmp]);
p.push_back(tmp);
}
}
void proc() {
for (int i = 1; i <= m; ++i) {
int u, v;
cin >> u >> v;
ae(u, v);
}
int s = 0;
for (int i = 1; i <= n; ++i) {
if (inD[i] != outD[i]) {
cout << "NO\n";
return;
}
if (inD[i] > 0) {
s = i;
}
}
if (s != 0) {
dfs(s);
}
if (len(p) < m) {
cout << "NO\n";
return;
}
cout << "YES\n";
for (int i = m; --i >= 0;) {
cout << p[i] << " \n"[i == 0];
}
}
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin.exceptions(cin.failbit);
int tc;
cin >> tc >> n >> m;
if (tc == 1) {
undirected::proc();
} else {
directed::proc();
}
}