欧拉回路

定义

一个图，若能够找到一条路径，使得可以遍历完所有的边且不重复，则这样的图称为欧拉图，这条路径称为欧拉路径，若路径闭合也称为欧拉回路。

性质

• 连通无向图有欧拉路径的充要条件：图中度数是奇数的顶点的数量是 $0$ 或 $2$（一笔画问题）
• 连通无向图有欧拉回路的充要条件：图中所有点的度数都是偶数
• 如果连通无向图有 $2k$ 个奇数度数的顶点，那么它可以至少用 $k$ 笔画成

• 一个连通的有向图可以表示为一条不闭合的欧拉路径的充要条件是：某一个点的出度比入度多 $1$ ，另一个点的出度比入度少 $1$ ，前者为起点而后者为终点

• 一个连通的有向图可以表示为一条欧拉回路的充要条件是：每个顶点的出度和入度都相等

Hierholzer 算法

Hierholzer算法是一种可以在时间复杂度 $O(|E|)$ 内求出无向图或有向图的欧拉路径（如果有的话）的算法。

首先要判断这个图有没有欧拉路径，判断方法就是前面的定理

整个过程是递归实现的

• 选择任一顶点为起点，遍历所有相邻边。
• 深度搜索，访问相邻顶点。将经过的边都删除。
• 如果当前顶点没有相邻边，则将顶点入栈。
• 栈中的顶点倒序输出，就是从起点出发的欧拉回路。

无向图的欧拉路径

洛谷 P2731 [USACO3.3] 骑马修栅栏 Riding the Fences

#include <bits/stdc++.h>

int main() {
    freopen ("in.in", "r", stdin);
    int n, m; std::cin >> m; n = 1050;
    std::vector<std::vector<std::pair<int, int>>> g(n + 1);
    std::vector<int> du(n + 1, 0);
    int cnt = 0;
    for (int i = 1; i <= m; i++) {
        int x, y; std::cin >> x >> y;
        g[x].push_back({y, cnt++});
        g[y].push_back({x, cnt++});
        du[x]++; du[y]++;
    }

    for (int i = 1; i <= n; i++)
        std::sort(g[i].begin(), g[i].end());

    int st = -1; // 起点
    for (int i = 1; i <= n; i++) {
        if (du[i] > 0 && st == -1) st = i;
        if (du[i] & 1) {
            st = i;
            break;
        }
    }

    std::vector<int> vis(cnt, 0);
    std::stack<int> stk;
    std::function<void(int)> dfs = [&](int u) {
        for (auto &[v, id] : g[u]) {
            if (vis[id]) continue;
            vis[id] = 1; vis[id ^ 1] = 1;
            dfs(v);
        }
        stk.push(u);
    };

    dfs(st);

    while (!stk.empty()) {
        std::cout << stk.top() << "\n";
        stk.pop();
    }

    return 0;
}