代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 5500000
struct gg{
	int to,from,next;
}side[2*maxn];
int n,m,on[maxn],head[maxn],dfn[maxn],tot;
bool use=0;
int cnt=0;
void insert(int u,int v){
	struct gg a={v,u,head[u]};side[++cnt]=a;head[u]=cnt;return; 
}
bool visit[maxn],pre[maxn];
bool cir(int now,int fa){
	pre[now]=1;
	for(int i=head[now];i;i=side[i].next){
		int u=side[i].to;
		if(u==fa)continue;
		if(pre[u]){
			on[u]=1;on[now]=1;return 1;
		}
		if(cir(u,now)){
			if(on[now]){
				return 0;
			}
			else{
				on[now]=1;return 1;
			}
		}
	}
	return 0;
}
void dfs(int now,int mem){
	if(visit[now])return;
	visit[now]=1;
	dfn[++tot]=now;
	int data[maxn],tg=0;
	for(int i=head[now];i;i=side[i].next){
		int u=side[i].to;
		if(visit[u])continue;
		data[++tg]=u;
	}
	//cout<<data[1]<<endl;
	if(!tg)return;	
	sort(data+1,data+1+tg);
	for(int i=1;i<=tg;i++){
		if(visit[data[i]])continue;
		if(data[i]>mem&&mem&&!use){
			use=1;return;
		}
		if(on[now]&&on[data[i]]&&i!=tg){
			dfs(data[i],data[i+1]);
		}
		else if(tg==i){
			dfs(data[i],mem);
		}
		else{
			dfs(data[i],0);
		}
		
	}
	return;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v;scanf("%d%d",&u,&v);
		insert(u,v);insert(v,u);
	}
	if(n==m){
		use=0;
		cir(1,0);
		use=0;dfs(1,0);
	}
	else{
		use=1;
		dfs(1,0);
	}
	for(int i=1;i<=tot;i++){
		printf("%d ",dfn[i]);
	}
return 0;
}

评测结果