欧拉图，欧拉通路，欧拉回路，Hierholzer算法详解

文章目录

- 零、哥尼斯堡七桥问题
- 一、欧拉图
- - 1.1 相关概念
  - 1.2 判别法（不做证明）
  - 1.3 Hierholzer算法
  - 1.4 代码实现
  - - 1.4.1 邻接表存图
    - 1.4.2 链式前向星存图
- 二、OJ练习
- - 2.1 模板1
  - 2.2 模板2
  - 2.3 重新安排行程
  - 2.4 合法重新排列数对
  - 2.5 破解保险箱
  - 2.6 骑马修栅栏
  - 2.7 Domino
  - 2.7 词链
  - 2.8 瑞瑞的木棍
  - 2.9 无序字母对
  - 2.10 Watchcow S

零、哥尼斯堡七桥问题

这是个脍炙人口的问题。

莱昂哈德·欧拉在1735年提出：河中心有两个小岛。小岛与河的两岸有七条桥连接。在所有桥都只能走一遍的前提下，如何才能把这个地方所有的桥都走遍？

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

事实上，上图是不存在这样的方案的。

欧拉把问题的实质归于一笔画问题，即判断一个图是否能够遍历完所有的边而没有重复，而柯尼斯堡七桥问题则是一笔画问题的一个具体情境。

随着图论的发展，我们将上述问题归结为 欧拉路径 问题。

一、欧拉图

1.1 相关概念

欧拉回路：通过图中每条边恰好一次的回路

欧拉通路：通过图中每条边恰好一次的通路（注意通路无环）

**欧拉图：**具有欧拉回路的图

**半欧拉图：**具有欧拉通路但不具有欧拉回路的图

1.2 判别法（不做证明）

无向图：

存在欧拉通路的充要条件：
1. 非零度顶点是连通的
2. 恰有 2 个奇度顶点
存在欧拉回路的充要条件：
1. 非零度顶点是连通的
2. 顶点的度数都是偶数

有向图：

存在欧拉通路的充要条件：
1. 非零度顶点是弱连通的
2. 至多一个顶点的出度与入度之差为 1
3. 至多一个顶点的入度与出度之差为 1
4. 其他顶点的入度和出度相等
存在欧拉回路的充要条件：
1. 非零度顶点是强连通的
2. 每个顶点的入度和出度相等

1.3 Hierholzer算法

Hierholzer算法也称逐步插入回路法，是一个非常简单且容易理解的算法。

算法流程

根据无向图/有向图，要找的是欧拉通路/欧拉路径，选择起始结点u
遍历 u 的出边 (u, v)
- 删掉 (u, v)
- 递归进 v，做同样操作
- 回溯时，将边(u, v) 加入答案数组
最终得到的ans 就是欧拉路径的逆序，因为我们是在回溯后才加边的，所以是逆序
时间复杂度: O(M)

1.4 代码实现

1.4.1 邻接表存图

邻接表实现不容易写错, 而且对于某些恶心题目要求字典序输出我们可以直接排序

auto dfs = [&](auto&& self, int u) -> void {while (adj[u].size()) {int v = adj[u].back();adj[u].pop_back();self(self, v);ans.emplace_back(u, v);}
};

1.4.2 链式前向星存图

链式前向星主要防卡常, 但是逻辑没捋顺容易写挂.

链式前向星的删边操作就是标记数组 + 当前弧优化

// int head[N], idx;
// bool used[M];
// struct edge{
//     int v, nxt;
// } adj[M];auto dfs = [&](auto&& self, int u) -> void {for (int& i = head[u]; ~i; ) {int j = (t == 1 ? i / 2 + 1 : i + 1);if (used[j]) {i = adj[i].nxt;continue;}int v = adj[i].v, id = (t == 1 && (i & 1)) ? -j : j;used[j] = true;i = adj[i].nxt;self(self, v);ans.push_back(id);}
};

二、OJ练习

2.1 模板1

原题链接

P7771 【模板】欧拉路径 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路分析

由于要字典序最小的方案，我们用邻接表存图

AC代码

#include <bits/stdc++.h>
#include <ranges>
#define sc scanf
// #define DEBUG
using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using PII = std::pair<int, int>;
constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1e18 + 7;
constexpr int P = 1E9 + 7;
constexpr double eps = 1E-6;void solve()
{int n, m;std::cin >> n >> m;std::vector<std::vector<int>> adj(n);std::vector<int> in(n), out(n);for (int i = 0, u, v; i < m; ++ i) {std::cin >> u >> v;-- u, -- v;adj[u].push_back(v);++ out[u], ++ in[v];}int st = -1, ed = -1;for (int i = 0; i < n; ++ i) {if (out[i] - in[i] == 1) {if (~st) {std::cout << "No\n";return;}elsest = i;}else if (in[i] - out[i] == 1) {if (~ed) {std::cout << "No\n";return;}elseed = i;}else if(in[i] != out[i]) {std::cout << "No\n";return ;}std::sort(adj[i].begin(), adj[i].end(), std::greater<int>());}if (st == -1) st = 0;std::vector<PII> ans;auto dfs = [&](auto&& self, int u) -> void {while (adj[u].size()) {int v = adj[u].back();adj[u].pop_back();self(self, v);ans.emplace_back(u, v);}};dfs(dfs, st);std::reverse(ans.begin(), ans.end());std::cout << ans[0].first + 1 << ' ';for (auto& [u, v] : ans)std::cout << v + 1 << ' ';
}int main()
{
#ifdef DEBUGfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifstd::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);int _ = 1;// std::cin >> _;while (_--)solve();return 0;
}

2.2 模板2

原题链接

#10105. 「一本通 3.7 例 1」欧拉回路

思路分析

对于无向图, 这里边集数组下标从0开始, 所以对应原边编号是 i / 2 + 1, 根据奇偶决定是否乘-1

删边也是根据编号删除, 因为无向图的双向边走一个方向另一个方向就不能走了

AC代码

#include <bits/stdc++.h>
constexpr int N = 1E5 + 10, M = 4E5 + 10;int head[N], idx;
int n, m, t;
int in[N], out[N];
bool used[M];
struct edge{int v, nxt;
} adj[M];void addedge(int u, int v) {adj[idx] = { v, head[u] }, head[u] = idx ++;
}auto init = []() {memset(head, -1, sizeof head);return 0;
}();int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);std::ios::sync_with_stdio(false), std::cin.tie(nullptr);std::cin >> t;std::cin >> n >> m;for (int i = 1, u, v; i <= m; ++ i) {std::cin >> u >> v;addedge(u, v);if (t == 1)addedge(v, u);++ in[v], ++ out[u];}std::vector<int> ans;auto dfs = [&](auto&& self, int u) -> void {for (int& i = head[u]; ~i; ) {int j = (t == 1 ? i / 2 + 1 : i + 1);if (used[j]) {i = adj[i].nxt;continue;}int v = adj[i].v, id = (t == 1 && (i & 1)) ? -j : j;used[j] = true;i = adj[i].nxt;self(self, v);ans.push_back(id);}};for (int i = 1; i <= n; ++ i) {if (t == 1) {if (in[i] + out[i] & 1) {std::cout << "NO\n";return 0;}}else {if (in[i] != out[i]) {std::cout << "NO\n";return 0;}}}if (idx)dfs(dfs, adj[idx - 1].v);if (ans.size() != m) {std::cout << "NO\n";return 0;}std::reverse(ans.begin(), ans.end());std::cout << "YES\n";for (int x : ans)std::cout << x << ' ';return 0;
}

2.3 重新安排行程

原题链接

332. 重新安排行程

思路分析

题目意思就是让求欧拉路径, 而且起点给了, 那也不用管什么通路/回路, 出入度了, 直接跑板子

记得对边进行排序

AC代码

class Solution {
public:vector<string> findItinerary(vector<vector<string>>& tickets) {unordered_map<string, vector<string>> adj;for (auto& e : tickets)adj[e[0]].emplace_back(e[1]);for (auto& p : adj)sort(p.second.rbegin(), p.second.rend());vector<string> res;auto dfs = [&](auto&& self, const string& u) -> void {while (adj[u].size()) {string v = adj[u].back();adj[u].pop_back();self(self, v);}res.emplace_back(u);};dfs(dfs, "JFK");std::reverse(res.begin(), res.end());return res;}
};

2.4 合法重新排列数对

原题链接

2097. 合法重新排列数对

思路分析

又是板子题, 由于没说是通路还是回路, 所以我们先按无向图找通路起点, 找不到就说明是回路, 随便找个起点就行

AC代码

python3

class Solution:def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:g = defaultdict(list)ind, outd = Counter(), Counter()for x, y in pairs:g[x].append(y)ind[y] += 1outd[x] += 1st = pairs[0][0]for x, y in pairs:if outd[x] - ind[x] == 1:st = xbreakret = []def dfs(x: int) -> None:while g[x]:y = g[x].pop()dfs(y)ret.append([x, y])dfs(st)return ret[::-1]

cpp

class Solution {
public:vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {unordered_map<int, vector<int>> g;unordered_map<int, int> outd, ind;for(auto& e : pairs){int x = e[0], y = e[1];g[x].push_back(y);outd[x] ++, ind[y] ++;}int st = pairs[0][0];for(auto& e : pairs){int x = e[0], y = e[1];if(outd[x] == ind[x] + 1) {st = x;break;}}    vector<vector<int>> res;function<void(int)> dfs = [&](int x){while(g[x].size()){int y = g[x].back();g[x].pop_back();dfs(y);res.push_back({x, y});}};dfs(st);reverse(res.begin(), res.end());return res;}
};

2.5 破解保险箱

原题链接

753. 破解保险箱

思路分析

我们将 n - 1 位数看为节点，则有 $k^{n-1}$ 个结点，每个结点有 k 个入边和出边

从 $a_1 a_2 ... a_{n-1}$ 到 $a_2 a_2 ... a_{n-1}x$ 这条边相当于输入了数字x

每个节点加上一条出边就可以得到一个n位数，也就是说每个结点可以得到k个n位数， $k^{n-1}$ 个结点一共可以得到 $k^{n}$ 个n位数，不重不漏

由于每个结点出度入度相等都为k，且强连通，于是图中存在欧拉回路，我们求欧拉回路即可得答案

实际中我们不需要建图，用哈希表标记结点即可

AC代码

class Solution {
public:string crackSafe(int n, int k) {unordered_set<int> st;string res;int base = pow(10, n - 1);auto dfs = [&](auto&& self, int u) -> void {for (int i = 0; i < k; ++ i) {int v = u * 10 + i;if (!st.count(v)) {st.insert(v);self(self, v % base);res += '0' + i;}}};dfs(dfs, 0);return res += string(n - 1, '0');}
};

2.6 骑马修栅栏

原题链接

洛谷 P2731 骑马修栅栏

思路分析

题意比较直白，就是求欧拉路径，套板子即可

由于没给点数，而数据量较小且要求字典序，于是使用邻接矩阵存图

AC代码

#include <bits/stdc++.h>
// #define DEBUG
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;constexpr int N = 500;void solve() {int m;std::cin >> m;std::unordered_map<int, std::unordered_map<int, int>> adj;std::unordered_map<int, int> d;for (int i = 0, u, v; i < m; ++ i) {std::cin >> u >> v;++ adj[u][v];++ adj[v][u];++ d[u], ++ d[v];}int st = 0;for (int u = 1; u <= N; ++ u) {if (!st && d.count(u))st = u;if (d[u] & 1) {st = u;break;}}std::vector<int> ans;auto dfs = [&](auto&& self, int u) -> void {for (int v = 1; v <= 500; ++ v)if (adj[u][v]) {-- adj[u][v];-- adj[v][u];self(self, v);}ans.push_back(u);};dfs(dfs, st);std::reverse(ans.begin(), ans.end());for (int x : ans) std::cout << x << '\n';
}auto init_ = []{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);return 0;
} ();int main() {#ifdef DEBUGfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);#endif     int t = 1;// std::cin >> t;while (t --)solve();return 0;
}

2.7 Domino

原题链接

SGU 101 Domino

思路分析

乍一看让找哈密顿路径，要是存在的话还行，我们通常用状压dp解决，但是不存在的话就麻烦了。

我们继续观察，发现我们把数字当作结点，每块骨牌当作边，问题就转化成了一个有n条边的图，我们要让每条边出现一次

这就变成了欧拉路径问题了

本题时间限制卡在0.25 second，但是点也就7个，边也就200条，还是跑得飞快的

注意无向图存在欧拉通路和欧拉回路的条件

AC代码

#include <bits/stdc++.h>
// #define DEBUG
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;const int N = 7, M = 210;
int head[N], idx;
struct edge {int v, nxt, id;
} adj[M];void addedge(int u, int v, int id) {adj[idx] = { v, head[u], id }, head[u] = idx ++;
}int d[N];
bool used[M];auto clear = []{memset(head, -1, sizeof head);// memset(used, 0, sizeof used);// memset(d, 0, sizeof d);// idx = 0;return 0;
}();void solve() {int n;std::cin >> n;for (int i = 1, u, v; i <= n; ++ i) {std::cin >> u >> v;addedge(u, v, i), addedge(v, u, -i);++ d[u], ++ d[v];}int st = -1, c = 0;for (int i = 0; i < N; ++ i) {if (d[i] & 1)st = i, ++ c;if (st == -1 && d[i])st = i;}if (c != 2 && c != 0) {std::cout << "No solution";return;}std::vector<std::pair<int, char>> ans;auto dfs = [&](auto&& self, int u) -> void {for (int& i = head[u]; ~i; ) {int v = adj[i].v, id = adj[i].id;i = adj[i].nxt;if (used[abs(id)]) {continue;}used[abs(id)] = true;self(self, v);ans.emplace_back(abs(id), id > 0 ? '+' : '-');}};dfs(dfs, st);if (ans.size() != n) {std::cout << "No solution";return;}std::reverse(ans.begin(), ans.end());for (auto& [id, c] : ans)std::cout << id << ' ' << c << '\n';}auto init_ = []{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);return 0;
} ();int main() {#ifdef DEBUGfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);#endif     int t = 1;// std::cin >> t;while (t --)solve();return 0;
}

2.7 词链

原题链接

洛谷 P1127 词链

思路分析

如果将单词看作点，则会是一个哈密顿路径问题

如果我们把单词看作边，就是一个欧拉回路问题

我们将单词看作边，开头字母结尾字母看作点

那么就会得到26个点，n条边的有向图

我们求欧拉路径（通路或回路）即可

AC代码

#include <bits/stdc++.h>
// #define DEBUG
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;void solve() {int n;std::cin >> n;std::vector<std::string> words(n);std::vector<std::vector<std::pair<int, int>>> adj(26);std::vector<int> in(26), out(26);for (int i = 0; i < n; ++ i) {std::cin >> words[i];adj[words[i][0] - 'a'].emplace_back(i, words[i].back() - 'a');++ out[words[i][0] - 'a'], ++ in[words[i].back() - 'a'];}int st = -1, c0 = 0, c1 = 0;for (int i = 0; i < 26; ++ i) {if (out[i] - in[i] == 1) {st = i;++ c0;}if (in[i] - out[i] == 1) {++ c1;}if (st == -1 && out[i])st = i;}if (c0 > 1 || c1 > 1) {std::cout << "***";return;}for (auto& e : adj)std::sort(e.rbegin(), e.rend(), [&](auto& x, auto& y) {return words[x.first] < words[y.first];});std::vector<int> ans;auto dfs = [&](auto&& self, int u) -> void {while (adj[u].size()) {auto [e, v] = adj[u].back();adj[u].pop_back();self(self, v);ans.push_back(e);}};dfs(dfs, st);if (ans.size() != n) {std::cout << "***";return;}std::reverse(ans.begin(), ans.end());for (int i = 0; i < n; ++ i) {std::cout << words[ans[i]] << ".\n"[i == n - 1];}}auto init_ = []{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);return 0;
} ();int main() {#ifdef DEBUGfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);#endif     int t = 1;// std::cin >> t;while (t --)solve();return 0;
}

2.8 瑞瑞的木棍

原题链接

洛谷 P1333 瑞瑞的木棍

思路分析

只需要判断是否存在欧拉通路/回路即可

即度数判断+并查集判断连通性

AC代码

#include <bits/stdc++.h>
// #include <ranges>
// #define DEBUG
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;
constexpr double eps = 1e-9;std::unordered_map<std::string, std::string> p;std::string find(const std::string& a) {return p[a] == a ? a : p[a] = find(p[a]);
}void merge(const std::string& a, const std::string& b) {auto pa = find(a), pb = find(b);if (pa == pb) return;p[pb] = pa;
}void solve() {std::unordered_map<std::string, int> deg;std::string u, v;while (std::cin >> u >> v) {++ deg[u], ++ deg[v];if (!p.count(u))p.insert({u, u});if (!p.count(v))p.insert({v, v});merge(u, v);}int c = 0;for (auto& [u, d] : deg) {c += d & 1;}if (!deg.size()) {std::cout << "Possible";return;}if (c > 2) {std::cout << "Impossible";return;}auto root = p.begin() -> second;for (auto& [s, fa] : p) {if (fa != root) {std::cout << "Impossible";return;}}std::cout << "Possible";
}auto FIO = []{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);return 0;
} ();int main() {#ifdef DEBUGfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);#endif     int t = 1;// std::cin >> t;while (t --)solve();return 0;
}

2.9 无序字母对

原题链接

洛谷 P1341 无序字母对

思路分析

一个字母对就是一条边，跑板子。

注意字典序最小，我们要对邻接表排序，且选择最小起点。

AC代码

#include <bits/stdc++.h>
// #include <ranges>
// #define DEBUG
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;
constexpr double eps = 1e-9;void solve() {int n;std::cin >> n;std::unordered_map<char, std::vector<std::pair<char, int>>> adj;std::unordered_map<char, int> deg;for (int i = 0; i < n; ++ i) {std::string s;std::cin >> s;++ deg[s[0]], ++ deg[s[1]];adj[s[0]].push_back({ s[1], i + 1} );adj[s[1]].push_back({ s[0], -i - 1} );}int c = 0;char st = adj.begin() -> first;bool f = false;for (auto& [ch, d] : deg) {c += d & 1;if (d & 1) {if (!f)st = ch;elsest = std::min(st, ch);f = true;}else if(!f)st = std::min(st, ch);}if (c > 2) {std::cout << "No Solution";return;}for (auto& [u, e] : adj)std::sort(e.rbegin(), e.rend());std::string res;std::vector<bool> used(n + 1);auto dfs = [&](auto&& self, char u) -> void {while (adj[u].size()) {auto [v, id] = adj[u].back();adj[u].pop_back();if (used[abs(id)]) continue;used[abs(id)] = true;self(self, v);}res += u;};dfs(dfs, st);std::reverse(res.begin(), res.end());std::cout << res;
}auto FIO = []{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);return 0;
} ();int main() {#ifdef DEBUGfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);#endif     int t = 1;// std::cin >> t;while (t --)solve();return 0;
}

2.10 Watchcow S

原题链接

[洛谷 P6066 USACO05JAN]Watchcow S

思路分析

和无向图欧拉回路不同的是，该题要求所得的回路要经过每条边正向反向各一次

这就更简单了，我们把无向图欧拉回路板子中的used[]数组删掉就行了

这样求出来的欧拉回路会把正向边反向边都走一遍

注意起点是1

AC代码

#include <bits/stdc++.h>
// #include <ranges>
// #define DEBUG
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;
constexpr double eps = 1e-9;void solve() {int n, m;std::cin >> n >> m;std::vector<std::vector<int>> adj(n);for (int i = 0, a, b; i < m; ++ i) {std::cin >> a >> b;-- a, -- b;adj[a].push_back(b);adj[b].push_back(a);}std::vector<int> ans;auto dfs = [&](auto&& self, int u) -> void {while (adj[u].size()) {int v = adj[u].back();adj[u].pop_back();self(self, v);}ans.push_back(u);};dfs(dfs, 0);for (int x : ans) std::cout << x + 1 << '\n';
}auto FIO = []{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);return 0;
} ();int main() {#ifdef DEBUGfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);#endif     int t = 1;// std::cin >> t;while (t --)solve();return 0;
}