跳转至

欧拉路径⚓︎

欧拉路径（\text{Eulerian Path}）是指一条经过图中每条边恰好一次的路径。如果一条欧拉路径的起点和终点相同，则称为欧拉回路（\text{Eulerian Circuit}）。

使用 \text{Hierholzer} 算法可以有效地找到欧拉路径。以下是该算法的步骤：

  1. 检查图的性质：
    • 对于无向图，若存在欧拉回路，则所有顶点的度数均为偶数；若存在欧拉路径但不是回路，则恰有两个顶点的度数为奇数。
    • 对于有向图，若存在欧拉回路，则每个顶点的入度等于出度；若存在欧拉路径但不是回路，则恰有一个顶点的出度比入度大 1，另一个顶点的入度比出度大 1。
    • 除了度数条件外，还需要满足连通性条件：无向图中所有非零度顶点必须属于同一连通分量；有向图中所有非零度顶点在忽略边方向后也必须连通。
  2. 查找欧拉路径：
    • 选择一个起点：
      • 欧拉回路：可以从任意顶点开始。
      • 欧拉路径：无向图中选择一个度数为奇数的顶点作为起点；有向图中选择出度比入度大 1 的顶点作为起点。
    • 从起点出发，进行深度优先搜索。
    • 每次沿着某条边从某个顶点移动到另外一个顶点的时候，都需要删除这条边。
    • 当无法继续前进时，将当前顶点加入路径中，并回溯到上一个顶点继续搜索，直到所有边都被访问过。
  3. 输出结果：
    • 注意到只有那个入度与出度差为 1 的节点会导致死胡同，而该节点必然是最后一个遍历到的节点。因此可以改变入栈的规则，当遍历完一个节点所连的所有节点后，才将该节点入栈（即逆序入栈）。
    • 最终路径需要反转以获得正确的顺序。
骑马修栅栏 Riding the Fences

给定一个无向图，要求输出一条经过每条边恰好一次的路径，且路径字典序最小。题目保证至少存在一条欧拉路径。

C++
#include <algorithm>
#include <cstdint>
#include <functional>
#include <iostream>
#include <map>
#include <utility>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  int m;
  cin >> m;
  map<int, vector<pair<int, int>>> g;  // (邻接点, 边id)
  vector<bool> used(m, false);         // 边是否被使用过

  int start = INT32_MAX;  // 起点
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    g[u].emplace_back(v, i);
    g[v].emplace_back(u, i);
    start = min({start, u, v});  // 记录编号最小点
  }

  // 找起点, 奇数度点个数
  int odd = 0;
  for (const auto &[u, vs] : g) {
    if (vs.size() % 2 == 1) {
      start = odd == 0 ? u : start;  // 从编号较小的奇数度点开始
      ++odd;
    }
    sort(g[u].begin(), g[u].end(),
         greater<>());  // 为了字典序最小, 逆序存储邻接点
  }
  // 无法构成欧拉路径
  if (odd != 0 && odd != 2) { return 0; }
  vector<int> path;
  auto hierholzer = [&](auto &&self, int u) -> void {
    while (!g[u].empty()) {
      auto [v, id] = g[u].back();  // 取最后一个邻接点
      g[u].pop_back();
      if (used[id]) { continue; }  // 已使用过则跳过
      used[id] = true;
      self(self, v);
    }
    path.push_back(u);  // 回溯时记录路径
  };

  hierholzer(hierholzer, start);
  // 未使用所有边, 图不连通
  if (path.size() != m + 1) { return 0; }

  reverse(path.begin(), path.end());
  for (int v : path) { cout << v << "\n"; }
  return 0;
}
【模板】欧拉路径

给定一个有向图，要求输出一条经过每条边恰好一次的路径，且路径字典序最小。如果不存在欧拉路径，则输出 "No"。

C++
#include <algorithm>
#include <cstdint>
#include <functional>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  int n, m;
  cin >> n >> m;
  vector<vector<pair<int, int>>> g(n + 1);  // (邻接点, 边id)
  vector<int> in_degree(n + 1, 0);
  vector<int> out_degree(n + 1, 0);
  vector<bool> used(m, false);  // 边是否被使用过

  int start = INT32_MAX;  // 起点
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    g[u].emplace_back(v, i);
    out_degree[u]++;
    in_degree[v]++;
    start = min({start, u, v});  // 记录编号最小点
  }

  // 找起点, 入度比出度大1的点为终点, 出度比入度大1的点为起点
  int start_nodes = 0, end_nodes = 0;
  for (int u = 1; u <= n; ++u) {
    if (out_degree[u] - in_degree[u] == 1) {
      start = u;
      start_nodes++;
    } else if (in_degree[u] - out_degree[u] == 1) {
      end_nodes++;
    } else if (in_degree[u] != out_degree[u]) {
      cout << "No\n";
      return 0;
    }
    sort(g[u].begin(), g[u].end(),
         greater<>());  // 为了字典序最小, 逆序存储邻接点
  }
  // 无法构成欧拉路径
  if ((start_nodes != 1 || end_nodes != 1) && (start_nodes != 0 || end_nodes != 0)) {
    cout << "No\n";
    return 0;
  }
  vector<int> path;
  auto hierholzer = [&](auto &&self, int u) -> void {
    while (!g[u].empty()) {
      auto [v, id] = g[u].back();  // 取最后一个邻接点
      g[u].pop_back();
      if (used[id]) { continue; }  // 已使用过则跳过
      used[id] = true;
      self(self, v);
    }
    path.push_back(u);  // 回溯时记录路径
  };

  hierholzer(hierholzer, start);

  if (path.size() != m + 1) {  // 未使用所有边, 图不连通
    cout << "No\n";
    return 0;
  }
  reverse(path.begin(), path.end());
  for (int v : path) { cout << v << " "; }
  cout << "\n";
  return 0;
}

评论