代码

#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int M = 20055 ;
using namespace std ;
inline int read() {
    char c = getchar() ; int x = 0 , w = 1 ;
    while(c>'9'||c<'0') { if(c=='-') w = -1 ; c = getchar() ; }
    while(c>='0'&&c<='9') { x = x*10+c-'0' ; c = getchar() ; }
    return x*w ;
}

int n , m ;
int hea[M] , num ;
int temp[M] , tot , Ans[M] ;
bool vis[M] , use[M] ;
vector < int > e[M] ;
int dfn[M] , low[M] , cnt ;
int bel[M] , st[M] , top , sz ;
bool exist[M] ;
int id[5005][5005] ;
struct E {
    int Nxt , From , to ;
} edge[M] ;
inline void add_edge(int from , int to) {
    edge[++num].Nxt = hea[from] ;
    edge[num].From = from ;
    edge[num].to = to ; hea[from] = num ;
}

void Dfs(int u , int father) {
    temp[++tot] = u ;
    for(int i = hea[u] ; i ; i = edge[i].Nxt) {
        int v = edge[i].to ;
        if(v == father || vis[i]) continue ;
        Dfs(v , u) ;
    }
}
inline void Solve1() {
    Dfs(1 , 1) ;
    for(int i = 1 ; i <= tot ; i ++) printf("%d ",temp[i]) ;
}
void tarjan(int u , int father) {
    dfn[u] = low[u] = ++cnt ; exist[u] = true ; st[++top] = u ;
    for(int i = hea[u] ; i ; i = edge[i].Nxt) {
        int v = edge[i].to ;
        if(v == father) continue ;
        if(!dfn[v]) {
            tarjan(v , u) ;
            low[u] = min(low[u] , low[v]) ;
        }
        if(exist[v]) low[u] = min(low[u] , dfn[v]) ;
    }
    if(dfn[u] == low[u]) {
        ++ sz ;
        while(st[top + 1] != u) {
            bel[st[top]] = sz ;
            exist[st[top --]] = false ;
        }
    }
}
inline bool chkmin() {
    for(int i = 1 ; i <= tot ; i ++){
        if(Ans[i] > temp[i]) return true ;
        else if(Ans[i] < temp[i]) return false ;
    }
    return false ;
}
inline void Solve2() {
    for(int i = 1 ; i <= n ; i ++)
        if(!dfn[i])
            tarjan(i , i) ;
    memset(Ans , 63 , sizeof(Ans)) ;
    for(int i = 1 , u , v ; i <= num ; i ++) {
        u = edge[i].From , v = edge[i].to ;
        if(bel[u] != bel[v]) continue ;
        if(use[id[u][v]] || use[id[v][u]]) continue ;
        use[id[u][v]] = use[id[v][u]] = true ;
        vis[id[u][v]] = vis[id[v][u]] = true ;
        tot = 0 ;
        Dfs(1 , 1) ;
        vis[id[u][v]] = vis[id[v][u]] = false ;
        if(chkmin())
            for(int j = 1 ; j <= tot ; j ++)
                Ans[j] = temp[j] ;
    }
    for(int i = 1 ; i <= n ; i ++) printf("%d ",Ans[i]) ;
}
int main() {
    n = read() , m = read() ;
    for(int i = 1 , u , v ; i <= m ; i ++) {
        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()) ;
        for(int j = e[i].size() - 1 , v ; j >= 0 ; j --) {
            v = e[i][j] ;
            add_edge(i , v) ;
            id[i][v] = num ;
        }
    }
    if(m == n - 1) {
    	Solve1() ;
    	return 0 ;
    }
    else Solve2() ;
    return 0 ;
}

评测结果