(树的深度优先遍历, DFS, 基环树) $(O(N^2)$)

如果是一棵树，则我们一定从1号点开始遍历，每次按编号从小到大的顺序遍历所有子节点，得到的DFS序列的字典序最小。

这道题目给定的树还有可能是基环树，即树中有一个环。 此时可以发现：不论如何遍历，我们一定会遍历其中 (n-1) 条边，因此可以枚举删掉哪条边，然后再用在树中遍历的方式求出最小字典序即可。

对每个点的所有邻边排序可以在初始化时进行，不需要在每次枚举时都重新排序。

我们不需要先将环找出来，直接暴力枚举所有边，最终更新答案时判断一下树是否连通即可。

另外还有一个优化的效果很明显：

• 在DFS过程中维护当前序列和最优序列的大小关系，如果发现当前序列的字典序一定大于最优序列，则可以直接退出。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
#define x first
#define y second
const int N=5010;
int n,m;
vector<int> g[N];
PII edge[N];
int ans[N],path[N];
int cnt,state;
int du,dv;
bool st[N];
bool dfs(int u)
{
    path[cnt++]=u;
    st[u]=true;
    if(state==0) //说明前面是相等的
    {
        if(path[cnt-1]<ans[cnt-1]) state=-1; //说明当前路径更小一些
        else if(path[cnt-1]>ans[cnt-1]) //说明当前路径不合法
        {
            state=1;
            return true;
        }
    }
    for(auto x:g[u])
    {
        if(x==du&&u==dv||x==dv&&u==du) continue;//说明这个是被删除的路径
        if(!st[x]&&dfs(x)) return true;//不合法的路径
    }
    return false;
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        edge[i]={a,b};
        g[a].push_back(b),g[b].push_back(a);
    }
    for(int i=1;i<=n;i++)
    {
        sort(g[i].begin(),g[i].end());//按照字典序从小到大排序
    }
    memset(ans,0x3f,sizeof ans);//初始化无穷大
    if(n==m)
    {
        for(int i=0;i<m;i++)
        {
            du=edge[i].x,dv=edge[i].y;
            memset(st,0,sizeof st);
            cnt=state=0;//初始化
            dfs(1);
            if(cnt==n&&state<0) //当前树连通且字典序更小
            {
                memcpy(ans,path,sizeof ans);
            }
        }
    }
    else
    {
        dfs(1);
        memcpy(ans,path,sizeof ans);
    }
    for(int i=0;i<n;i++)
    {
        cout<<ans[i]<<" ";
    }
    return 0;
}