欧拉路径c++算法模板

以下是一个求解欧拉路径的 C++ 算法模板（无向图）：

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 1005;

vector<int> G[MAXN];
int deg[MAXN];   // 记录每个顶点的度数

vector<int> ans; // 存储欧拉路径

void dfs(int u) {
    for (int i = 0; i < G[u].size(); ++i) {
        int v = G[u][i];
        if (deg[v]) {   // 只要边存在，就一定能够走
            --deg[u];
            --deg[v];
            dfs(v);
        }
    }
    ans.push_back(u);   // 回溯时将经过的点加入路径中
}

int main() {
    int n, m;
    cin >> n >> m;  // 输入顶点数和边数
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
        ++deg[u];
        ++deg[v];   // 维护每个顶点的度数
    }

    int cnt = 0;    // 统计度数为奇数的顶点个数
    int st = 1;     // 欧拉路径的起点
    for (int i = 1; i <= n; ++i) {
        if (deg[i] & 1) {
            ++cnt;
            st = i;
        }
    }

    // 不存在欧拉路径的情况
    if (cnt != 0 && cnt != 2) {
        cout << "No Euler Path!" << endl;
        return 0;
    }

    dfs(st);    // 从起点开始搜索欧拉路径

    // 判断路径是否经过了所有的边
    if (ans.size() != m + 1) {
        cout << "No Euler Path!" << endl;
        return 0;
    }

    // 输出欧拉路径
    for (int i = ans.size() - 1; i >= 0; --i) {
        cout << ans[i] << " ";
    }
    cout << endl;

    return 0;
}

该算法的时间复杂度为 $O(m)$，其中 $m$ 表示边数。