代码

#include<bits/stdc++.h>

using namespace std;

inline int read(){
	int ret=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}

const int maxn=5005,maxe=10005;

int n,m;
int tot=0,lnk[maxn],nxt[maxe],to[maxe];
pair<int,int> edges[maxn];
bool vis[maxn];

int ans[maxn],now[maxn];
pair<int,int> now_block;

int son[maxn][maxn];

void add_edge(int x,int y){
	tot++; to[tot]=y;
	nxt[tot]=lnk[x];lnk[x]=tot;
}

bool check(int x,int y){
	if (x==now_block.first && y==now_block.second) return false;
	if (y==now_block.first && x==now_block.second) return false;
	return true;
}

void DFS(int x){
	vis[x]=true; now[++now[0]]=x;
	for (int i=1;i<=son[x][0];i++)
		if (!vis[son[x][i]] && check(x,son[x][i])) DFS(son[x][i]);
}

bool smaller(){
	for (int i=1;i<=n;i++)
		if (now[i]<ans[i]) return true; else
		if (now[i]>ans[i]) return false;
	return false;
}

int main(){
	#ifdef DEBUG
		freopen("testdata.in","r",stdin);
		freopen("my.out","w",stdout);
	#endif
	n=read();m=read();
	for (int i=1;i<=m;i++){
		int x=read(),y=read();
		add_edge(x,y);add_edge(y,x);
		son[x][++son[x][0]]=y;
		son[y][++son[y][0]]=x;
		edges[i]=make_pair(x,y);
	}
	for (int i=1;i<=n;i++) sort(son[i]+1,son[i]+1+son[i][0]);

	if (m==n-1){
		DFS(1);
		for (int i=1;i<=n;i++) printf("%d ",now[i]);
		printf("\n");
	} else {
		for (int i=1;i<=m;i++){
			memset(vis,0,sizeof(vis));
			now_block=edges[i]; now[0]=0;
			DFS(1);
			if (now[0]!=n) continue;
			if (ans[0]==0 || smaller())
				for (int j=0;j<=n;j++) ans[j]=now[j];
		}
		for (int i=1;i<=n;i++) printf("%d ",ans[i]);
		printf("\n");
	}
	return 0;
}

评测结果