欧拉路径与欧拉回路CSP-S

💡 核心思想

欧拉路径是经过图中每条边恰好一次的路径。欧拉回路是起点和终点相同的欧拉路径。无向图中：所有点度数都是偶数 → 存在欧拉回路；恰好两个点度数为奇数 → 存在欧拉路径（从其中一个奇度点出发）。有向图中：所有点入度=出度 → 欧拉回路；恰好一个点出度=入度+1，一个点入度=出度+1 → 欧拉路径。

🎯 直觉理解

想象你在一个公园里散步，要求每条路都走一遍，但不能重复。如果所有路口都是偶数条路交汇，你可以从任何地方出发，最后回到起点（欧拉回路）。如果恰好有两个路口是奇数条路，你必须从其中一个出发，到另一个结束（欧拉路径）。这就是邮递员问题。

📝 算法流程

1. 判断图是否连通
2. 统计各点度数（无向图）或出入度（有向图）
3. 判断是否存在欧拉路径/回路
4. 用 Hierholzer 算法求路径：DFS 遍历每条未访问的边，走到死胡同时入栈，回溯
5. 逆序输出栈即为欧拉路径

$$\text{无向图欧拉回路：} \forall v, \deg(v) \equiv 0 \pmod 2$$

$$\text{有向图欧拉回路：} \forall v, \text{in}(v) = \text{out}(v)$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;

// Hierholzer 算法求欧拉回路（无向图）
vector> g[10005]; // (邻居, 边编号)
bool used[20005];
stack path;

void euler(int u) {
    for (auto& [v, eid] : g[u]) {
        if (used[eid]) continue;
        used[eid] = true;
        euler(v);
    }
    path.push(u);
}

int main() {
    int n = 4, m = 4;
    // 建图：1-2, 2-3, 3-4, 4-1（一个环）
    g[1].push_back({2, 1}); g[2].push_back({1, 1});
    g[2].push_back({3, 2}); g[3].push_back({2, 2});
    g[3].push_back({4, 3}); g[4].push_back({3, 3});
    g[4].push_back({1, 4}); g[1].push_back({4, 4});
    
    euler(1);
    while (!path.empty()) {
        cout << path.top() << " ";
        path.pop();
    }
    cout << endl;
    return 0;
}

⚠️ 常见坑点

📚 相关题目