1 欧拉路
给定一张图,要求连续走过所有边,每条边恰好使用一次,顶点可以重复经过。这样的行走称为欧拉路;起点与终点相同时,称为欧拉回路。
这里沿用竞赛中的“欧拉路”称呼,不要求顶点互不重复。本篇把回路也包含在欧拉路之内;需要区分时,把起终点不同的情形称为开放的欧拉路。
与普通 图的遍历 不同,访问对象是边。不能用 visited[u] 阻止再次进入顶点,否则会漏掉经过同一顶点的其他边。
先判断是否存在,再用 Hierholzer 算法构造。以下允许重边和自环,顶点编号为
2 无向图判定
一次经过中间顶点,使用一条边进入,再使用一条边离开,所以边总是成对出现。只有起点与终点可以各剩下一条边。
因此,忽略孤立点后,所有有边的顶点必须连通,并满足下列一种情况:
| 奇度顶点数 | 结论 | 起点 |
|---|---|---|
| 存在欧拉回路 | 任意有边顶点 | |
| 存在开放的欧拉路 | 任意一个奇度顶点 | |
| 其他 | 不存在欧拉路 | 无 |
度数条件与连通性缺一不可。 两个互不相连的三角形,所有顶点度数都是偶数,仍不可能连续走完全部边。
无向自环贡献两次度数;两点之间的平行边分别计数。孤立点没有边需要覆盖,不影响其他部分是否存在欧拉路。
3 有向图判定
有向边只能沿指定方向使用。记
忽略入度与出度都为
在此基础上,度数应满足:
| 情形 | 度数条件 | 起点 |
|---|---|---|
| 欧拉回路 | 所有点 |
任意有出边顶点 |
| 开放的欧拉路 | 恰有一个点 |
差值为 |
其他情况均无解。不能只检查每个差值属于
图中只能从
不需要额外要求原图强连通。例如只有一条边
4 Hierholzer 算法
4.1 拼接回路
先考虑回路。沿未使用的边一直走,度数平衡保证不会停在起点以外,最终回到起点,形成一条闭合行走。
若还有边没有使用,就从当前行走上仍有剩余边的顶点出发,再找一条闭合行走,插入原来的位置。反复拼接,直到覆盖全部边。
开放的欧拉路也可以这样理解:临时连接终点与起点,先求回路,再从临时边处断开。这个补边只用于解释和证明,后面的代码直接从合法起点构造。
4.2 逆序记录
显式维护拼接位置较繁琐。用栈保存当前行走,在无边可走时记录顶点,就能自动完成拼接:
- 起点入栈。
- 栈顶
还有未使用的边 ,标记该边,将 入栈。 - 栈顶没有可用边,将它加入答案并弹栈。
- 重复直到栈空,最后反转答案。
记录的是出栈顺序,不是第一次走到某点的顺序。
4.3 示例
考虑无向边
此时在
| 操作 | 栈(左为栈底) | 已记录的答案 |
|---|---|---|
| 走到 |
空 | |
| 弹出 |
||
| 走完剩余小环 | ||
| 依次弹出剩余顶点 | 空 |
反转得到
5 正确性
先证明平衡且连通的图存在欧拉回路。
从有边顶点出发,沿未使用边延长行走。若停在其他顶点,无向图中进入后还应剩下一条配对的边;有向图中则因进入次数比离开次数多一次,还应有一条出边。因此第一次停止只能回到起点。
取走一条闭合行走后,各顶点的剩余度数仍为偶数,或剩余入出度仍相等。若还有边,连通性保证当前行走中某点接触剩余边;有向图中,剩余入出度平衡也保证该点有剩余出边。从这里继续得到闭合行走,拼入后仍连续,且不重复使用边。反复执行,便覆盖全部边。
对于开放的欧拉路,在终点与起点之间补边后满足回路条件;求出回路并删去补边,就得到从起点到终点的欧拉路。结合前面的必要性分析,判定条件既必要又充分。
栈实现把已经无边可走的末尾先逆序保存,退回尚有剩余边的顶点后继续展开。新得到的回路在反转后位于已保存的后缀之前,等价于上述拼接。边号标记保证不重复走边,最终反转得到合法顺序。
6 实现要点
6.1 边号
一条无向边在邻接表中存两条记录,两条记录共用同一个 id。走过任意一个方向后,都将 used[id] 设为真。
重边的端点可能相同,边号必须不同。自环也保留:它在无向邻接表中出现两次,通过边号保证只走一次。
有向边只存一次。它可以仅依靠扫描位置避免重用;这里保留相同的边号与构造函数,便于对照两版代码。
6.2 扫描位置
cur[u] 表示顶点
如果每次回到顶点都从邻接表开头寻找可用边,重边多或度数大时,会反复检查同一批记录,不能保证线性复杂度。
6.3 连通性
代码不另建图检查连通性,而是在度数条件通过、起点选择正确之后,检查记录的顶点数是否为
每使用一条边,就入栈一次;起点额外入栈一次。因此答案长度等于已使用边数加一。若少于
不能省略度数判定。例如有向边
7 无向图代码
两份模板均输入 NO,不保证字典序最小。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200000 + 5;
const int maxm = 500000 + 5;
struct Edge {
int to, id;
};
vector<Edge> g[maxn];
int deg[maxn], cur[maxn];
bool used[maxm];
// 栈与答案保存的是行走中的顶点,可重复,容量要按边数设置。
int st[maxm + 1], path[maxm + 1];
int top = 0, length = 0;
void hierholzer(int s) {
st[top++] = s;
while (top) {
int u = st[top - 1];
int &i = cur[u]; // 保留扫描位置,不从头反复寻找可用边
while (i < (int)g[u].size() && used[g[u][i].id]) ++i;
if (i == (int)g[u].size()) {
path[length++] = u; // 无边可走时记录,答案逆序产生
--top;
} else {
auto [v, id] = g[u][i++];
used[id] = true; // 两条邻接记录共享边号,只能使用一次
st[top++] = v;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int id = 0; id < m; ++id) {
int u, v;
cin >> u >> v;
g[u].push_back({v, id});
g[v].push_back({u, id});
++deg[u];
++deg[v]; // 若 u == v,自环恰好贡献两次度数
}
int s = 0, first = 0, odd = 0;
for (int u = 1; u <= n; ++u) {
if (deg[u] && !first) first = u;
if (deg[u] % 2) {
++odd;
if (!s) s = u; // 开放的欧拉路必须从奇度点出发
}
}
if (odd != 0 && odd != 2) {
cout << "NO\n";
return 0;
}
if (!s) s = first ? first : 1; // 回路从有边点出发;无边时取顶点 1
hierholzer(s);
if (length != m + 1) { // 度数条件通过后,用覆盖边数检查连通性
cout << "NO\n";
return 0;
}
reverse(path, path + length);
for (int i = 0; i < length; ++i) {
if (i) cout << ' ';
cout << path[i];
}
cout << '\n';
return 0;
}
示例输入:
5 5
1 2
2 5
2 3
3 4
4 2
本代码输出:
1 2 3 4 2 5
8 有向图代码
度数判定改为检查入出度差,建图时只加入给定方向。无解仍输出 NO。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200000 + 5;
const int maxm = 500000 + 5;
struct Edge {
int to, id;
};
vector<Edge> g[maxn];
int indeg[maxn], outdeg[maxn], cur[maxn];
bool used[maxm];
int st[maxm + 1], path[maxm + 1]; // 顶点可重复出现,容量按边数设置
int top = 0, length = 0;
void hierholzer(int s) {
st[top++] = s;
while (top) {
int u = st[top - 1];
int &i = cur[u];
while (i < (int)g[u].size() && used[g[u][i].id]) ++i;
if (i == (int)g[u].size()) {
path[length++] = u; // 当前点无出边可走,逆序记录答案
--top;
} else {
auto [v, id] = g[u][i++];
used[id] = true;
st[top++] = v;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int id = 0; id < m; ++id) {
int u, v;
cin >> u >> v;
g[u].push_back({v, id}); // 有向边只加入一个方向
++outdeg[u];
++indeg[v];
}
int s = 0, first = 0, starts = 0, ends = 0;
for (int u = 1; u <= n; ++u) {
if (outdeg[u] && !first) first = u;
int delta = outdeg[u] - indeg[u];
if (delta == 1) {
++starts;
s = u;
} else if (delta == -1) {
++ends;
} else if (delta != 0) {
cout << "NO\n";
return 0;
}
}
// 只能全部平衡,或恰有一对起终点;不能只检查差值是否属于 {-1,0,1}。
if (!((starts == 0 && ends == 0) || (starts == 1 && ends == 1))) {
cout << "NO\n";
return 0;
}
if (!s) s = first ? first : 1;
hierholzer(s);
if (length != m + 1) { // 度数条件通过后,检查是否覆盖全部有向边
cout << "NO\n";
return 0;
}
reverse(path, path + length);
for (int i = 0; i < length; ++i) {
if (i) cout << ' ';
cout << path[i];
}
cout << '\n';
return 0;
}
将上面的输入视为五条有向边,本代码输出同样的序列,每一步也都符合箭头方向。
9 字典序
若题目要求顶点序列字典序最小,先选择最小的合法起点,再让每个点的邻接表按终点递增排列,仍用上述出栈后反转的构造:
for (int u = 1; u <= n; ++u) {
sort(g[u].begin(), g[u].end(), [](const Edge &a, const Edge &b) {
return a.to < b.to;
});
}
把排序放在建图完成之后、调用 hierholzer 之前。两份模板已经选择最小的合法起点:开放路取最小奇度点或唯一的有向起点,回路取最小有边顶点。
排序控制尝试顺序,回溯负责把提前到达终点的分支放到后面。不能改成“每次选最小邻点,走不动就立即输出结束”。
若输出的是单词等边的标签,还需按题意比较边的标签,并记录进入各栈帧的边号。只有顶点序列,不能区分同端点的不同单词。
10 复杂度与边界
- 不排序时,建图、度数判定与构造的总时间为
,空间为 。 - 排序后,总时间为
,空间不变。 - 模板容量为
、 。行走栈和答案最多保存 个顶点,不能只按点数开空间。 - 当
时,本篇约定单个顶点 1表示长度为零的欧拉回路。具体题目若另有输出约定,应相应调整。 - 度数满足但有边部分不连通时,必须输出无解。不要从多个连通块分别构造后直接拼接。
- 每次构造都会消耗
cur、used和栈状态;再次运行或处理多组数据前需要清空。
11 练习
11.1 手算
- 两个三角形只共用一个顶点,能否存在欧拉回路?这与存在割点是否矛盾?
- 无向图有边
,两个顶点的度数分别是多少? - 有向图有两条
和两条 ,能否存在欧拉回路?
参考结果
- 存在。公共顶点度数为
,其他点为 ,且图连通。欧拉回路允许顶点重复,存在割点不妨碍覆盖全部边。 - 分别为
,两个点均为奇度点。可走 。 - 存在。两点入出度均为
,可走 ;平行边分别使用。
11.2 推荐题目
| 层次 | 题目 | 训练内容 |
|---|---|---|
| 有向图 | luogu P7771: 【模板】欧拉路径 | 有向欧拉路与最小字典序;需要排序,并将无解输出改为题目要求的 No。 |
| 无向图 | luogu P2731 | 无向图、重边与最小字典序;输入只给边数,答案每行输出一个顶点,需调整输入输出。 |
| 建模 | luogu P1127: 词链 | 单词首尾字母作顶点,单词作有向边;按单词排序并保存边号,输出单词序列。 |
12 相关题解
暂无相关题解