C++14(g++5.4) 解法, 执行用时: 545ms, 内存消耗: 36192K, 提交时间: 2019-10-22 16:43:15

#include<bits/stdc++.h>
using namespace std;
const int maxn=5005;
int n,m;
int X[maxn],Y[maxn],g[maxn][maxn],ans[maxn],ans1[maxn];
int visit[maxn],cnt=0,ok=0;

void dfs1(int x ){
	visit[x]=1;
	ans[++cnt]=x;
	for(int i=1;i<=n;i++){
		if(visit[i]==0 && g[x][i]==1) {
		dfs1(i);
		}
	}
    return ;
}

int dfs2(int x){
	if(x>ans[cnt+1] && (ok==0)) return 0;
	if(x<ans[cnt+1]) ok=1;
	visit[x]=1;
	ans1[++cnt]=x;
	for(int i=1;i<=n;i++){
		if((g[x][i]==1) && (visit[i]==0 )) {
		if(dfs2(i)==0) return 0;
		}
	}
    return 1 ;
}

void solve() {
	for(int i=1;i<=n;i++) ans[i]=n;
	for(int i=0;i<m;i++){
		int x=X[i],y=Y[i];
		memset(visit,0,sizeof(visit));
		cnt=0;ok=0;
		g[x][y]=0;g[y][x]=0;
		dfs2(1);
		g[x][y]=1;g[y][x]=1;
		if(cnt==n){for(int i=1;i<=n;i++) ans[i]=ans1[i];	} 		
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int x,y;
		cin>>x>>y;
		X[i]=x;Y[i]=y;
		g[x][y]=g[y][x]=1;
	}
	memset(ans,0x3f,sizeof(ans));
	if(m==n-1) dfs1(1);
	else solve();
	
	cout<<ans[1];
    for(int i=2;i<=n;i++) 
	{cout<<" "<<ans[i]; }
    cout<<endl;
    
	return 0;
} 

C++(clang++ 11.0.1) 解法, 执行用时: 13ms, 内存消耗: 952K, 提交时间: 2022-08-09 11:06:45

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e3+10;
int vis[N],l[N],r[N],u,v,cnt,tr;
vector<int>g[N],s(N),ans(N,N);
int dfs(int id){
	if(tr){
		if(id>ans[cnt])return 1;
		if(id<ans[cnt])tr=0;
	}
	vis[id]=1;
	s[cnt++]=id;
	for(int i:g[id]){
		if(!vis[i]&&!(i==u&&id==v)&&!(i==v&&id==u)){
			if(dfs(i))return 1;
		}
	}
	return 0;
}
void solve(){
	int n,m;
	cin>>n>>m;
	for(int i=0;i<m;i++){
		cin>>l[i]>>r[i];
		g[l[i]].push_back(r[i]);
		g[r[i]].push_back(l[i]);
	}
	for(int i=1;i<=n;i++)sort(g[i].begin(),g[i].end());
	if(n==m+1){
		dfs(1);
		for(int i=0;i<n;i++)printf("%d ",s[i]);
		return;
	}
	for(int i=0;i<m;i++){
		memset(vis,0,sizeof vis);
		cnt=0,tr=1;
		u=l[i],v=r[i];
		dfs(1);
		if(cnt==n)ans=s;
	}
	for(int i=0;i<n;i++)printf("%d ",ans[i]);
}
int main(){
	int t=1;
	while(t--)solve();
	return 0;
}