c++算法按字典序数输出的欧拉路径模板

以下是按字典序数输出的欧拉路径模板的 C++ 实现：

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

vector<set<int>> graph;

void dfs(int u, vector<int> &path) {
    while (!graph[u].empty()) {
        int v = *graph[u].begin();
        graph[u].erase(v);
        graph[v].erase(u);
        dfs(v, path);
    }
    path.push_back(u);
}

vector<int> euler_path(int n, vector<pair<int, int>>& edges) {
    // 构建邻接表
    graph.assign(n, set<int>());
    for (auto& edge : edges) {
        graph[edge.first].insert(edge.second);
        graph[edge.second].insert(edge.first);
    }

    // 找到起点
    int start = 0;
    while (graph[start].empty() && start < n) {
        start++;
    }

    // 检查是否存在欧拉路径
    int odd_vertices = 0;
    for (int u = 0; u < n; u++) {
        if (graph[u].size() % 2 == 1) {
            odd_vertices++;
        }
    }
    if (odd_vertices != 0 && odd_vertices != 2) {
        cout << "No Euler path found." << endl;
        return {};
    }

    // 求解欧拉路径
    vector<int> path;
    dfs(start, path);
    reverse(path.begin(), path.end());
    return path;
}

int main() {
    int n = 5;
    vector<pair<int, int>> edges = {{0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 0}, {0, 2}, {2, 4}};
    vector<int> path = euler_path(n, edges);
    for (int u : path) {
        cout << u << " -> ";
    }
    cout << endl;
    return 0;
}

在这个模板中，我们首先构建了一个邻接表来表示图的结构。然后我们检查是否存在欧拉路径。如果存在欧拉路径，我们从起点开始，按照字典序的顺序遍历图中的每一个节点，并把它们依次添加到路径中。最后，我们按照反向顺序输出路径即可。