A1378 [NOIP2018 提高组 T4] 旅行

#include <bits/stdc++.h>
#include <vector>
using namespace std;

int n, m, ban;
vector<vector<pair<int, int>>> g; // (邻居, 边编号)
vector<int> seq;
vector<char> vis;

// 从 1 出发做 DFS：邻居按编号升序，记录首次访问顺序
void dfs(int u) {
    vis[u] = 1;
    seq.push_back(u);
    for (auto [v, e] : g[u]) {
        if (e == ban) continue;
        if (!vis[v]) dfs(v);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    g.assign(n + 1, {});
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back({v, i});
        g[v].push_back({u, i});
    }
    for (int i = 1; i <= n; ++i)
        sort(g[i].begin(), g[i].end());

    vector<int> best;
    ban = -1;
    if (m == n - 1) {
        // 图是一棵树，唯一的生成树就是它本身
        vis.assign(n + 1, 0);
        seq.clear();
        dfs(1);
        best = seq;
    } else {
        // m == n：图中恰有一个环，枚举删掉哪条边后取字典序最小的 DFS 序
        for (int e = 0; e < m; ++e) {
            ban = e;
            vis.assign(n + 1, 0);
            seq.clear();
            dfs(1);
            if ((int)seq.size() != n) continue; // 删边后不连通，不是生成树
            if (best.empty() || seq < best) best = seq;
        }
    }

    for (int i = 0; i < n; ++i) cout << best[i] << (i + 1 == n ? '\n' : ' ');
    return 0;
}