一本通-1341：【例题】一笔画问题（欧拉路+路径输出）

【题目描述】 如果一个图存在一笔画，则一笔画的路径叫做欧拉路，如果最后又回到起点，那这个路径叫做欧拉回路。

根据一笔画的两个定理，如果寻找欧拉回路，对任意一个点执行深度优先遍历；找欧拉路，则对一个奇点执行dfs，时间复杂度为O(m+n)，m为边数，n是点数。

【输入】 第一行n，m，有n个点，m条边，以下m行描述每条边连接的两点。

【输出】 欧拉路或欧拉回路，输出一条路径即可。

【输入样例】 5 5 1 2 2 3 3 4 4 5 5 1

【输出样例】 1 5 4 3 2 1

---

#include <bits/stdc++.h>

using namespace std;

int vertexNum, edgeNum;
vector<vector<int> > grid;
vector<vector<bool> > visit;
vector<int> degree;
stack<int> s;

void EulerCircuit(int from)
{
    for (int to = 1; to <= vertexNum; ++to) {
        if (grid[from][to] && !visit[from][to]) {
            visit[from][to] = visit[to][from] = true;
            EulerCircuit(to);
        }
    }
    s.push(from);
}


void solve()
{
    int start = 1;
    for (int i = 1; i <= vertexNum; ++i) {
        if (degree[i] & 1) { start = i; break; }
    }

    EulerCircuit(start);

    while (!s.empty()) {
        cout << s.top() << ' ';
        s.pop();
    }
    cout << endl;
}



int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> vertexNum >> edgeNum;
    grid.resize(vertexNum + 1, vector<int>(vertexNum + 1, 0));
    visit.resize(vertexNum + 1, vector<bool>(vertexNum + 1, false));
    degree.resize(vertexNum + 1, 0);

    for (int i = 0; i < edgeNum; ++i) {
        int from, to; cin >> from >> to;
        grid[from][to] = grid[to][from] = 1;
        ++degree[from], ++degree[to];
    }

    solve();

    return 0;
}

注意欧拉路径的输出需要用辅助栈才能正序输出。