代码

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
static int n,m;
static vector<int> adj[5005];
static int vis[5005], cur[5005], bestseq[5005], cnt;
static int bu,bv;
static void dfs(int u){
    vis[u]=1; cur[cnt++]=u;
    for(size_t i=0;i<adj[u].size();i++){
        int v=adj[u][i];
        if(vis[v]) continue;
        if((u==bu&&v==bv)||(u==bv&&v==bu)) continue;
        dfs(v);
    }
}
int main(){
    if(scanf("%d %d",&n,&m)!=2) return 0;
    for(int i=0;i<m;i++){int a,b;scanf("%d %d",&a,&b);adj[a].push_back(b);adj[b].push_back(a);}
    for(int i=1;i<=n;i++) sort(adj[i].begin(),adj[i].end());
    if(m==n-1){
        bu=bv=-1; cnt=0; memset(vis,0,sizeof vis); dfs(1);
        for(int i=0;i<n;i++) printf("%d%c",cur[i],i+1<n?' ':'\n');
        return 0;
    }
    static int deg[5005]; static char rem[5005];
    static int q[5005];
    for(int i=1;i<=n;i++) deg[i]=(int)adj[i].size();
    int qh=0,qt=0;
    for(int i=1;i<=n;i++) if(deg[i]==1) q[qt++]=i;
    while(qh<qt){
        int u=q[qh++]; rem[u]=1;
        for(size_t i=0;i<adj[u].size();i++){ int v=adj[u][i]; if(!rem[v] && --deg[v]==1) q[qt++]=v; }
    }
    static int cu[5005],cv[5005]; int nc=0;
    for(int u=1;u<=n;u++) if(!rem[u]) for(size_t i=0;i<adj[u].size();i++){ int v=adj[u][i]; if(!rem[v]&&u<v){ cu[nc]=u; cv[nc]=v; nc++; } }
    int have=0;
    for(int e=0;e<nc;e++){
        bu=cu[e]; bv=cv[e]; cnt=0; memset(vis,0,sizeof vis); dfs(1);
        if(!have){ memcpy(bestseq,cur,sizeof(int)*n); have=1; }
        else { for(int i=0;i<n;i++){ if(cur[i]!=bestseq[i]){ if(cur[i]<bestseq[i]) memcpy(bestseq,cur,sizeof(int)*n); break; } } }
    }
    for(int i=0;i<n;i++) printf("%d%c",bestseq[i],i+1<n?' ':'\n');
    return 0;
}

评测结果