旅行

除了起点外，恰好访问了n-1个新的点，也就是整个过程只会经过n-1条边那经过的边就形成了一棵生成树。若原图就是一棵树，我们考虑如何计算最优字典序。我们选择以1号点为起点。可以发现题目中的限制等 价于对原图的一次dfs，形成的序列就是dfs序。所以我们只需要确定访问孩子的顺序使得dfs序字典序最小，只需要按照编号从小到大访问孩子。

#include<bits/stdc++.h>
using namespace std;
const int maxn=5005;
int n,m,a[maxn][maxn],len[maxn],fa[maxn],dep[maxn],cir[maxn],cnt,b[maxn],tot,ban1,ban2,ans[maxn];
int read()
{
    int x=0,w=1;
 char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-') 
  ch=getchar();
    if(ch=='-') 
  w=0,ch=getchar();
    while(ch>='0'&&ch<='9') 
  x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return w?x:-x;
}
void dfs1(int u,int f)
{
    fa[u]=f;
 dep[u]=dep[f]+1;
    for(int i=1;i<=len[u];++i)
 {
        int v=a[u][i];
  if(v==f) 
   continue;
        if(!dep[v]) 
   dfs1(v,u);
        else if(dep[v]<dep[u])
  {
            for(int j=u;j!=v;j=fa[j]) 
    cir[++cnt]=j;
            cir[++cnt]=v;
        }
    }
}
void dfs2(int u,int f)
{
    b[++tot]=u;
    for(int i=1;i<=len[u];++i)
 {
        int v=a[u][i];
  if(v==f||(u==ban1&&v==ban2)||(u==ban2&&v==ban1)) 
   continue;
        dfs2(v,u);
    }
}
void check()
{
    for(int i=1;i<=n;++i)
 {
        if(b[i]>ans[i]) 
   return;
        if(b[i]<ans[i])
  {
   memcpy(ans,b,sizeof(ans));
   return;
  }
    }
}
int main()
{
    n=read();
 m=read();
    for(int i=1;i<=m;++i)
 {
        int u=read(),v=read();
        a[u][++len[u]]=v;
        a[v][++len[v]]=u;
    }
    for(int i=1;i<=n;++i) 
  sort(a[i]+1,a[i]+len[i]+1);
    dfs1(1,0);
    memset(ans,63,sizeof(ans));
    if(m==n-1)
  dfs2(1,0),check();
    else
 {
        for(int j=1;j<cnt;++j)
            ban1=cir[j],ban2=cir[j+1],tot=0,dfs2(1,0),check();
        ban1=cir[cnt],ban2=cir[1],tot=0,dfs2(1,0),check();
    }
    for(int i=1;i<=n;++i) 
  printf("%d ",ans[i]);
    puts("");
 return 0;
}