代码

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

using namespace std;
const int M=5e5+10;

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];
int stk[M],top;
void dfs(int a,int b){
	vis[a]=1;stk[++top]=a;
	for(int i=0,sz=vec[a].size(),v;i<sz;++i){
		v=vec[a][i];
		if(v==b) continue;
		if(vis[v]){
			for(;top>0&&stk[top]!=v;--top){
				cir[stk[top]]=1;
			}	cir[v]=1;
			return;
		}else{
			dfs(v,a);
		}
	}
	vis[stk[top--]]=0;
}
int ans[M],tot,p1,p2;
void dfs_ans(int a,int b){
	ans[++tot]=a;
	for(int i=0,sz=vec[a].size(),v;i<sz;++i){
		v=vec[a][i];
		if((a==p1&&v==p2)||(a==p2&&v==p1)) continue;
		if(v==b) continue;
		dfs_ans(v,a);
	}
}
int fip;
void find_first_p(int a,int b){
	for(int i=0,sz=vec[a].size(),v;i<sz;++i){
		if(fip) return;
		v=vec[a][i];
		if(v==b) continue;
		if(cir[v]){fip=v;return;}
		find_first_p(v,a);
	}
}
void dfs_cir(int a,int b,int nex){
	for(int i=0,sz=vec[a].size(),v;i<sz;i++){
		if(p1&&p2) return;
		v=vec[a][i];
		if(v==b||!cir[v]) continue;
		if(v>=nex){
			p1=a;p2=v;
			return;
		}
		dfs_cir(v,a,nex);
	}
}
int n,m,a,b;
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,1);
	}else{
		dfs(1,1);
		if(cir[1])fip=1;
		else find_first_p(1,1);
		int fi=0,nex=0;
		for(int i=0,sz=vec[fip].size();i<sz;i++){
			if(cir[vec[fip][i]]){
				if(!fi)fi=vec[fip][i];
				else if(!nex){
					nex=vec[fip][i];
					break;
				}
			}
		}
		dfs_cir(fip,fip,nex);
		dfs_ans(1,1);
	}
	for(int i=1;i<=n;i++){
		printf("%d ",ans[i]);
	}
	return 0;
}

评测结果