代码

#include<vector> 
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
const int M=5e5+10;
const int inf=1e9;
vector <int> vec[M];
void add(int a,int b){
	vec[a].push_back(b);
	vec[b].push_back(a);
}
bool vis[M],cir[M],finded;
int stk[M],up;
void dfs_cir(int a,int b){
	vis[a]=1;stk[++up]=a;
	for(int i=0,sz=vec[a].size(),v;i<sz;i++){
		v=vec[a][i];
		if(finded) return;
		if(v==b) continue;
		if(vis[v]){
			finded=1;
			for(;up&&stk[up]!=v;--up){
				cir[stk[up]]=1;
			}	cir[stk[up--]]=1;
			return;
		}else{
			dfs_cir(v,a);
		}
	}
	vis[stk[up--]]=0;
}

int ans[M],tot,ls[M],top,delet;
void dfs_ans(int a,int nex){
	vis[a]=1;ans[++tot]=a;
	int p=top+1,q;
	for(int i=0,sz=vec[a].size(),v;i<sz;i++){
		v=vec[a][i];
		if(!vis[v])ls[++top]=v;
	}
	q=top;
	for(int i=p,j=p+1;i<=q;i=j,j++){
		if(vis[ls[i]]) continue;
		while(j<=q&&vis[ls[j]])++j;
		if(j<=q)dfs_ans(ls[i],ls[j]);
		else if(!delet&&cir[a]&&cir[ls[i]]&&ls[i]>nex)delet=1;
		else dfs_ans(ls[i],nex);
	}
}
int a,b,n,m;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&a,&b);
		add(a,b);
	}
	for(int i=1;i<=n;i++){sort(vec[i].begin(),vec[i].end());}
	if(m==n-1){
		dfs_ans(1,inf);
	}else{
		dfs_cir(1,1);
		memset(vis,0,sizeof(vis));
		dfs_ans(1,inf);
	}
	for(int i=1;i<n;i++) printf("%d ",ans[i]);printf("%d",ans[n]);
	return 0;
} 

评测结果