代码

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

using namespace std;

#define pb push_back

const int N=500010,inf=0x3f3f3f3f;
int n,m,ans[N],num,lim=-1,outlim[N],out=500005,st[N],tp;
bool vis[N],incir[N];
vector <int> e[N];

inline void re(int &x)
{
	x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+(ch^48), ch=getchar();
}

void cirl(int x,int fa)
{
	vis[x]=1;
	st[++tp]=x;
	int i,y,siz=e[x].size();
	for(i=0;i<siz;++i)
	{
		y=e[x][i];
		if(y==fa) continue;
		if(vis[y])
		{
			lim=x;
			while(st[tp]!=y)
			{
				incir[st[tp]]=1;
				--tp;
			}
			return;
		}
		cirl(y,x);
		if(lim!=-1) return;
	}
	--tp;
}

void dfs(int x)
{
	ans[++num]=x;
	vis[x]=1;
	if(out!=500006&&outlim[x]!=inf) out=x;
	int i,y,siz=e[x].size();
	for(i=0;i<siz;++i)
	{
		y=e[x][i];
		if(vis[y]) continue;
		if(incir[y]&&!vis[lim])
		{
			if(outlim[out]!=inf)
			{
				if(y>outlim[out]&&!vis[outlim[out]]) {out=500006; continue;}
			}
			else
			{
				if(y>lim) {out=500006; continue;}
			}
		}
		dfs(y);
	}
	if(x==out) out=500006;
}

int main()
{
//	freopen("travel.in","r",stdin);
//	freopen("travel.out","w",stdout);
	
	int i,j,u,v;
	re(n); re(m);
	for(i=1;i<=m;++i)
	{
		re(u); re(v);
		e[u].pb(v); e[v].pb(u);
	}
	for(i=1;i<=n;++i) sort(e[i].begin(),e[i].end());
	cirl(1,0);
	memset(outlim,0x3f,sizeof(outlim));
	for(i=1;i<=n;++i)
		if(incir[i]&&e[i].size()>2)
		{
			u=e[i].size()-1;
			for(j=u;j>=0;--j)
			{
				v=e[i][j];
				if(incir[v]) break;
				outlim[i]=v;
			}
		}
	memset(vis,0,sizeof(vis));
	dfs(1);
	for(i=1;i<=n;++i) printf("%d ",ans[i]);
	
//	fclose(stdin); fclose(stdout);
	return 0;
}

评测结果