代码

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
inline int read(){
	int ans=0;
	char a=getchar();
	while('0'>a||a>'9'){
		a=getchar();
	}
	while('0'<=a&&a<='9'){
		ans=ans*10+a-'0';
		a=getchar();
	}
	return ans;
}
vector<int>edge[5005];
struct node{
	int next,tot;
};
vector<node>edge1[5005];
int n,m;
int out[5005],fst[5005],nout[5005],now,cut;
bool been[5005];
void dfs(int u){
	been[u]=1;
	for(int i=0;i<edge[u].size();i++){
		int v=edge[u][i];
		if(!been[v]){
			nout[now++]=v;
			dfs(v);
		}
	}
}
void dfs1(int u){
	been[u]=1;
	for(register int i=0;i<edge1[u].size();i++){
		node v=edge1[u][i];
		if(v.tot==cut)continue;
		if(been[v.next]==0){
			nout[now++]=v.next;
			dfs1(v.next);
		}
	}
}
inline bool cmp(node x,node y){
	return x.next<y.next;
}
int main(){
	n=read(),m=read();
	if(n-1==m){
		for(int i=1;i<=m;i++){
			int x=read(),y=read();
			edge[x].push_back(y);
			edge[y].push_back(x);
		}
		for(int i=1;i<=n;i++){
			sort(edge[i].begin(),edge[i].end());
		}
		fst[1]=-1;
		now=2;
		nout[1]=1;
		dfs(1);
		for(int i=1;i<=n;i++){
			printf("%d ",nout[i]);
		}
	}
	else{
		for(register int i=1;i<=m;i++){
			int x=read(),y=read();
			edge1[x].push_back(node{y,i});
			edge1[y].push_back(node{x,i});
		}
		for(register int i=1;i<=n;i++){
			sort(edge1[i].begin(),edge1[i].end(),cmp);
		}
		bool flag=0;
		for(cut=1;cut<=m;cut++){
			memset(been,0,sizeof(been));
			nout[1]=1;
			now=2;
			dfs1(1);
			if(now>n){
				if(!flag){
					for(int i=1;i<=n;i++){
						out[i]=nout[i];
					}
				}
				else{
					bool flag1=1;
					for(register int i=1;i<=n;i++){
						if(nout[i]>out[i]){
							flag1=0;
							break;
						}
						if(nout[i]<out[i])break;
					}
					if(flag1){
						for(int i=1;i<=n;i++){
							out[i]=nout[i];
						}
					}
				}
				flag=1;
			}
		}
		for(register int i=1;i<=n;i++){
			printf("%d ",out[i]);
		}
		puts("");
	}
	return 0;
}

评测结果