代码

#include<bits/stdc++.h>
using namespace std;
int m,n,a1[5001],a2[5001],a3,ans1,d[5001][5001],d1[5001],ans[5001],e[10001],e1[10001],e2[5001],u,v,e5,e6,ans2[5001];
bool b[5001],ok,ok1;
void abc(int c)
{
	++ans1;
	if(ans1>n)return;
	ans[ans1]=c;
	for(int i=1;i<=m;++i)
	{
		if(a1[i]==c&&(b[a2[i]])==0)
		{
			d[c][++d1[c]]=a2[i];
		}
		else if(a2[i]==c&&(b[a1[i]])==0)
		{
			d[c][++d1[c]]=a1[i];
		}
	}
	b[c]=1;
	sort(d[c],d[c]+d1[c]+1);
	for(int i=1;i<=d1[c];++i)
	{
		abc(d[c][i]);
	}
}
void abc1(int c)
{
	if(b[c])return;
	b[c]=1;
	int e3=e2[c];
	d1[c]=0;
	while(e3)
	{
		if(e3==e5||b[e[e3]]||e3==e6)
		{
			e3=e1[e3];
			continue;
		}
		d[c][++d1[c]]=e[e3];
		e3=e1[e3];
	}
	sort(d[c]+1,d[c]+d1[c]+1);
	for(int i=1;i<=d1[c];i++)
	{
		if(ok==0)
		{
			if(d[c][i]>ans[++ans1])
			{
				ok1=1;
				return;
			}
			if(d[c][i]<ans[ans1])
			{
				ok=1;
				ans[ans1]=d[c][i];
			}
		}
		else ans[++ans1]=d[c][i];
		abc1(d[c][i]);
		if(ok1)return;
	}
}
int main()
{
	//freopen("travel.in","r",stdin);
	//freopen("travel.out","w",stdout);
	scanf("%d%d",&n,&m);
	if(m==n-1)
	{
		for(int i=1;i<=m;++i)
		{
			scanf("%d%d",&a1[i],&a2[i]);
		}
		abc(1);
		for(int i=1;i<=n;i++)printf("%d ",ans[i]);
		return 0;
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&u,&v);
		e[(i<<1)-1]=v;
		e1[(i<<1)-1]=e2[u];
		e2[u]=(i<<1)-1;
		e[i<<1]=u;
		e1[i<<1]=e2[v];
		e2[v]=i<<1;
	}
	memset(ans,0x3f,sizeof(ans));
	memset(ans2,0x3f,sizeof(ans2));
	ans[1]=1;
	ans2[1]=1;
	for(int j=1;j<=m;j++)
	{
		e5=j<<1;
		e6=e5-1;
		ans1=1;
		ok=0;
		ok1=0;
		memset(b,0,sizeof(b));
		abc1(1);
		if(ok&&ans1==n)for(int i=1;i<=n;i++)ans2[i]=ans[i];
		else for(int i=1;i<=n;i++)ans[i]=ans2[i];
	}
	for(int i=1;i<=n;i++)printf("%d ",ans2[i]);
	return 0;
}

评测结果