代码

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

const int maxn = (int)(5e5) + 5;
vector<int> nxt[maxn];
int vi[maxn];
int fa[maxn];
int s, t;

void dfs(int x, int f) {
    vi[x] = vi[f] + 1;
    fa[x] = f;
    sort(nxt[x].begin(), nxt[x].end());
    for (int v : nxt[x]) {
        if (!vi[v]) dfs(v, x);
        else if (v != f && vi[v] < vi[x]) {
            int a = x;
            for (int w : nxt[v]) if (!vi[w]) {
                a = w; break;
            }
            int u = fa[x];
            while (fa[u] != v) {
                if (u > a) {
                    s = fa[u];
                    t = u;
                }
                u = fa[u];
            }
        }
    }
}

void print(int x) {
    vi[x] = 1;
    printf("%d ", x);
    for (int v : nxt[x]) if (!vi[v] && (x != s || v != t)) print(v);
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        nxt[u].push_back(v);
        nxt[v].push_back(u);
    }
    dfs(1, 0);
    memset(vi, 0, sizeof(vi));
    return print(1), putchar('\n'), 0;
}

评测结果