代码

// luogu-judger-enable-o2
#pragma GCC optimize(3)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
struct Edge{
	int to,next;
}e[10005];
int prt[5005],h[5005],cnt=1,n,m,used[5005],fa[5005],inans[5005],sss;
char TTT;
vector<int> a;
vector<int> ans;
void Add_Edge(int x,int y){
	e[++cnt].to=y;
	e[cnt].next=h[x];
	h[x]=cnt;
}
void dfs2(int point){
	if(used[point]&&prt[point]){
		dfs2(prt[point]);
		return ;
	}
	if(!inans[point])a.push_back(point),inans[point]=1;
	vector<int>tmp;
	for(int i=h[point];i;i=e[i].next){
		int y=e[i].to;
		if(!used[y]&&y!=prt[point])tmp.push_back(y);
	}
	used[point]=1;
	sort(tmp.begin(),tmp.end());
	for(int i=0;i<tmp.size();i++)dfs2(tmp[i]);
	if(!used[prt[point]])dfs2(prt[point]);
	used[point]=0;
}
void dfs1(int point,int nx,int ny){
	if(used[point])return ;
	used[point]=1;
	a.push_back(point);
	if(a>ans){
		TTT=1;
		return ;
	}
	vector<int> vec;
//	cout<<"now:"<<point<<endl;
	for(int i=h[point];i;i=e[i].next){
		int y=e[i].to;
		if(!used[y]&&!((point==nx&&y==ny)||(point==ny&&y==nx)))vec.push_back(y);//,cout<<y<<' ';
	}
//	puts("");
	sort(vec.begin(),vec.end());
	for(int i=0;i<vec.size();i++){
		dfs1(vec[i],nx,ny);
		if(TTT)return ;
	}
}
bool usedb[10005];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		Add_Edge(x,y);
		Add_Edge(y,x);
	}
	if(m==n-1){
		used[0]=1;
		dfs2(1);
		for(int i=0;i<n;i++)cout<<a[i]<<' ';
	}
	else {
		ans.resize(n);
		for(int i=0;i<n;i++)ans[i]=n+1;
		for(int i=1;i<=n;i++){
			for(int j=h[i];j;j=e[j].next){
				if(usedb[j])continue;
				TTT=0;
				usedb[j]=usedb[j^1]=1;
				memset(used,0,sizeof(used));
				//cout<<"duanbian:"<<i<<' '<<e[j].to<<endl;
				dfs1(1,i,e[j].to);
				if(a.size()==n)ans=min(ans,a);
				//for(int i=0;i<a.size();i++)cout<<a[i]<<' ';
				//cout<<endl;
				a.clear();
			}
		}
		for(int i=0;i<ans.size();i++)cout<<ans[i]<<' ';
	}
	return 0;
}

评测结果