代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define IO(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
#define I(x) freopen(x".in","r",stdin)
#define R(x) freopen(x".ini","r",stdin),freopen(x".in","w",stdout)
using namespace std;
const int N=501000;
inline int read(){
    register char c=getchar(),d=0;
    while(c>'9'||c<'0')d=c,c=getchar();
    register int r=0;
    while(c>='0'&&c<='9')r=(r<<1)+(r<<3)+c-'0',c=getchar();
    return d=='-'?-r:r;
}
inline void wt(int x){
    if(x/10)wt(x/10);
    putchar(x%10+'0');
}
inline void wtln(int x){
    if(x<0)x=-x,putchar('-');
    wt(x),putchar('\n');
}
inline void wtsp(int x){
    if(x<0)x=-x,putchar('-');
    wt(x),putchar(' ');
}
struct edge{
    int to,nt;
    inline void init(int t,int n){
        to=t,nt=n;
    }
}e[N<<1];
int h[N],c=1,x,y;
inline void adde(int f,int t){
    e[++c].init(t,h[f]),h[f]=c;
    e[++c].init(f,h[t]),h[t]=c;
}
int n,m;
int ans[N],tot;
namespace solve1{
    int tmp[N],cnt;
    int vis[N];
    inline void dfs(int pos){
        vis[pos]=1;
        ans[++tot]=pos;
        int l=cnt,r;
        for(int i=h[pos];i;i=e[i].nt)
            if(!vis[e[i].to])tmp[cnt++]=e[i].to;
        r=cnt;
        sort(tmp+l,tmp+r);
        for(int i=l;i<r;++i)
            dfs(tmp[i]);
    }
}
namespace solve2{
    int dele,px,py;
    int ste[N],stp[N],top;
    int cre[N],crp[N],cc,vis[N];
    inline bool fndc(int pos,int pi=0){
        int tps;
        vis[pos]=1;
        for(int i=h[pos];i;i=e[i].nt){
            tps=e[i].to;
            if(i==pi)continue;
            ste[++top]=i;
            stp[top]=pos;
            if(vis[tps]){
                while(1){
                    cre[++cc]=ste[top];
                    crp[cc]=stp[top];
                    if(stp[top--]==tps)break;
                }
                return 1;
            }else if(fndc(tps,i^1))return 1;
            if(ste[top]==i)--top;
        }
        return 0;
    }
    int tmp[N],cnt;
    inline void dfs(int pos){
        vis[pos]=1;
        ans[++tot]=pos;
        int l=cnt,r;
        for(int i=h[pos];i;i=e[i].nt)
            if(i!=dele&&(i^1)!=dele&&!vis[e[i].to])tmp[cnt++]=e[i].to;
        r=cnt;
        sort(tmp+l,tmp+r);
        for(int i=l;i<r;++i)
            dfs(tmp[i]);
    }
    inline void MAIN(){
        fndc(1);
        px=crp[1],py=crp[cc-1];
        if(cc==2){
            dele=cre[1];
        }else if(px<py){
            int p=1;
            while(crp[p]<py)++p;
            dele=cre[p];
        }else {
            int p=cc-1;
            while(crp[p-1]<px)--p;
            dele=cre[p];
        }
        memset(vis,0,sizeof vis);
        dfs(1);
    }
}
int main(){
    //IO("travel");
    n=read(),m=read();
    for(int i=1;i<=m;++i)
        adde(read(),read());
    if(n==m+1)solve1::dfs(1);
    else solve2::MAIN();
    for(int i=1;i<n;++i)
        wtsp(ans[i]);
    wtln(ans[n]);
}

评测结果