思路与算法

先按邻点编号排序。树直接从1做DFS；若m=n，用度数剥叶找唯一环，枚举删除每一条环边，在剩下的树上从1按邻点升序DFS，取字典序最小的首次到达序列。

正确性说明

任何合法遍历第一次到达每个非起点时，所用边组成一棵生成树；退回只能沿进入边，因此记录是这棵树的DFS序。树的所有生成树边固定；单环图的生成树恰删除一条环边，枚举穷尽全部可能。固定树上，较小未访问邻点先走能在第一个不同位置取得更小编号，不影响访问完其余子树，故排序DFS是该树最优序。枚举再取最小给全局最优。

复杂度

含图初始化与排序，O(n log n+n²)时间、O(n)空间；树分支为O(n log n)，单环最多n次线性DFS。

易错点

输出首次到达顺序，不是全部走路轨迹。树不能删桥；单环枚举只删环边。n=1可直接输出1。

参考代码（C++11）

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> g(n);
    vector<int> degree(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        g[u].push_back({v, i});
        g[v].push_back({u, i});
        degree[u]++;
        degree[v]++;
    }
    for (auto &v : g)
        sort(v.begin(), v.end());
    vector<int> on(n, 1), q;
    for (int i = 0; i < n; i++)
        if (degree[i] == 1)
            q.push_back(i);
    for (int i = 0; i < (int)q.size(); i++) {
        int u = q[i];
        on[u] = 0;
        for (auto e : g[u])
            if (on[e.first] && --degree[e.first] == 1)
                q.push_back(e.first);
    }
    vector<int> bans;
    if (m == n - 1)
        bans.push_back(-1);
    else
        for (int u = 0; u < n; u++)
            if (on[u])
                for (auto e : g[u])
                    if (on[e.first] && u < e.first)
                        bans.push_back(e.second);
    vector<int> best(n, n + 1);
    for (int ban : bans) {
        vector<int> seen(n), a;
        function<void(int)> dfs = [&](int u) {
            seen[u] = 1;
            a.push_back(u + 1);
            for (auto e : g[u])
                if (e.second != ban && !seen[e.first])
                    dfs(e.first);
        };
        dfs(0);
        if ((int)a.size() == n && a < best)
            best.swap(a);
    }
    for (int i = 0; i < n; i++) {
        if (i)
            cout << ' ';
        cout << best[i];
    }
    cout << "\n";
}