代码

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

const int N = 5e5 + 5;
int n, m, ans[N], stk[N], top;
vector<int> e[N];

int read() {
    int w = 0; char ch = getchar();
    while(ch > '9' || ch < '0') ch = getchar();
    while(ch >= '0' && ch <= '9') {
        w = w * 10 + ch - 48;
        ch = getchar();
    }
    return w;
}

namespace subtask1 {
    int dep = 0;
    void dfs(int u, int fa) {
        ans[++dep] = u;
        if (dep == n) return;
        for (int v : e[u]) {
            if (v == fa) continue;
            dfs(v, u);
        }
    }
    void main() {
        dfs(1, -1);
        for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
        putchar('\n');
        exit(0);
    }
}
namespace subtask2 {
    int dep = 0, g[N] = {}, vis[N] = {}, cnt, pd = 0, yel = N;
    void find(int u, int fa) {
        if (pd) return;
        stk[++top] = u; vis[u] = 1;
        for (int v : e[u]) {
            if (v == fa) continue;
            if (vis[v]) {
                while (stk[top] != v) g[stk[top--]] = 1;
                g[v] = 1;
                pd = 1;
                return;
            }
            find(v, u);
            if (pd) return;
        }
        top--;
    }
    void dfs(int u, int fa) {
        ans[++dep] = u; vis[u] = 1;
        for (int i = 0; i < e[u].size(); i++) {
            int v = e[u][i];
            if (v == fa || vis[v]) continue;
            if (!g[v]) dfs(v, u);
            else {
                if (!pd) {
                    int to = i == e[u].size() - 1 ? yel : e[u][i + 1];
                    if (to == fa) yel = i == e[u].size() - 2 ? yel : e[u][i + 2];
                    else yel = to;
                }
                if (yel < v && !pd) {
                    pd = 1; continue;
                }
                else dfs(v, u);
            }
        }
    }
    void main() {
        find(1, -1);
        pd = 0;
        memset(vis, 0, sizeof vis);
        dfs(1, -1);
        for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
        putchar('\n');
        exit(0);
    }
}

int main() {
    n = read(); m = read();
    for (int i = 1; i <= m; i++) {
        int u = read(), v = read();
        e[u].push_back(v); e[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) sort(e[i].begin(), e[i].end());
    if (n == m + 1) subtask1::main();
    else subtask2::main();
}

评测结果