代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<functional>
#include<cmath>
#include<vector>
#include<assert.h>
//using namespace std;
using std::min;
using std::max;
using std::swap;
using std::sort;
using std::reverse;
using std::random_shuffle;
using std::lower_bound;
using std::upper_bound;
using std::unique;
using std::vector;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
void open(const char *s){
#ifndef ONLINE_JUDGE
	char str[100];sprintf(str,"%s.in",s);freopen(str,"r",stdin);sprintf(str,"%s.out",s);freopen(str,"w",stdout);
#endif
}
void open2(const char *s){
#ifdef DEBUG
	char str[100];sprintf(str,"%s.in",s);freopen(str,"r",stdin);sprintf(str,"%s.out",s);freopen(str,"w",stdout);
#endif
}
int rd(){int s=0,c,b=0;while(((c=getchar())<'0'||c>'9')&&c!='-');if(c=='-'){c=getchar();b=1;}do{s=s*10+c-'0';}while((c=getchar())>='0'&&c<='9');return b?-s:s;}
void put(int x){if(!x){putchar('0');return;}static int c[20];int t=0;while(x){c[++t]=x%10;x/=10;}while(t)putchar(c[t--]+'0');}
int upmin(int &a,int b){if(b<a){a=b;return 1;}return 0;}
int upmax(int &a,int b){if(b>a){a=b;return 1;}return 0;}
const int N=500010;
vector<int> g[N],l[N];
int _x,_y;
vector<int> ans;
int c[2*N];
int b[N];
int e[N];
int f[N];
int d[N];
int n,m;
int t;
void dfs4(int x)
{
	ans.push_back(x);
	b[x]=1;
	for(auto v:g[x])
		if(!b[v]&&!e[v])
			dfs4(v);
}
void dfs(int x)
{
	if(e[x])
	{
		for(auto v:ans)
			printf("%d ",v);
		return;
	}
	b[x]=1;
	printf("%d ",x);
	for(auto v:g[x])
		if(!b[v])
			dfs(v);
}
void dfs2(int x,int fa,int dep)
{
	f[x]=fa;
	d[x]=dep;
	b[x]=1;
	for(auto v:g[x])
		if(v!=fa)
		{
			if(b[v])
			{
				if(d[v]>d[x])
				{
					_x=x;
					_y=v;
				}
			}
			else
				dfs2(v,x,dep+1);
		}
}
void dfs3(int x,int fa)
{
	f[x]=fa;
	for(auto v:g[x])
		if(v!=fa&&!e[v])
			dfs3(v,x);
}
int main()
{
	open("travel");
	n=rd();
	m=rd();
	int x,y;
	for(int i=1;i<=m;i++)
	{
		x=rd();
		y=rd();
		l[x].push_back(y);
		l[y].push_back(x);
	}
	for(int i=1;i<=n;i++)
		for(auto v:l[i])
			g[v].push_back(i);
	if(m==n-1)
	{
		dfs(1);
	}
	else
	{
		dfs2(1,0,1);
		memset(b,0,sizeof b);
		for(int i=_y;i!=f[_x];i=f[i])
			c[++t]=i;
		for(int i=1;i<=t;i++)
			e[c[i]]=1;
		for(int i=1;i<=t;i++)
			dfs3(c[i],0);
		for(int i=1;i<=t;i++)
			c[i+t]=c[i];
		int r;
		x=0;
		for(r=1;!e[r];r=f[r])
			if(e[f[r]])
				x=r;
		for(int i=1;i<=t;i++)
			if(c[i]==r)
			{
				r=i;
				break;
			}
		int l=r;
		r+=t;
		if(x)
			b[x]=1;
		int left=c[r-1];
		int right=c[l+1];
		int flag=-1;//1:right 0:left
		int next=-1;
		ans.push_back(c[l]);
		for(auto v:g[c[l]])
			if(!e[v]&&!b[v])
			{
				if(v<left&&v<right)
				{
					dfs4(v);
//					ans.push_back(v);
//					b[v]=1;
				}
				else if(left<right)
				{
					flag=0;
					break;
				}
				else
				{
					flag=1;
					break;
				}
			}
		for(auto v:g[c[l]])
			if(!e[v]&&!b[v])
			{
				next=v;
				break;
			}
		if(flag==-1)
		{
			if(left<right)
				flag=0;
			else
				flag=1;
		}
		if(flag==1)
		{
			if(next==-1)
				next=left;
		}
		else
		{
			if(next==-1)
				next=right;
			reverse(c+1,c+2*t+1);
			l=2*t-l+1;
			r=2*t-r+1;
			swap(l,r);
		}
		int now=l;
		while(now+1<r&&c[now+1]<next)
		{
			now++;
			ans.push_back(c[now]);
			for(auto v:g[c[now]])
				if(!b[v]&&!e[v])
				{
					if(v<c[now+1])
					{
						dfs4(v);
//						ans.push_back(v);
//						b[v]=1;
					}
					else
						break;
				}
			for(auto v:g[c[now]])
				if(!b[v]&&!e[v])
				{
					next=v;
					break;
				}
		}
		for(int i=now;i>l;i--)
		{
			for(auto v:g[c[i]])
				if(!b[v]&&!e[v])
				{
					dfs4(v);
//					b[v]=1;
//					ans.push_back(v);
				}
		}
		for(int i=r;i>now;i--)
		{
			if(i!=r)
				ans.push_back(c[i]);
			for(auto v:g[c[i]])
				if(!b[v]&&!e[v])
				{
					if(i>now+1&&c[i-1]<v)
						break;
					dfs4(v);
//					b[v]=1;
//					ans.push_back(v);
				}
		}
		for(int i=now+1;i<=r;i++)
		{
			for(auto v:g[c[i]])
				if(!b[v]&&!e[v])
				{
					dfs4(v);
//					b[v]=1;
//					ans.push_back(v);
				}
		}
		if(x)
			b[x]=0;
		dfs(1);
	}
	return 0;
}

评测结果