更好的阅读体验

Statement

给定一个 $n$ 点 $m$ 边无向连通图，不存在重边和自环。从任意一点出发，每次可以走向一个没去过的点或者按第一次访问当前点的路径回退。求一个字典序最小的遍历序列。

$n\leq 5e3$ , $m=n$ 或 $m=n-1$ .

Thoughts & Solution

这道题的关键显然在于数据范围。$m=n$ 或 $m=n-1$ ，就相当于是 一棵树或者基环树 。

60pts 树

对于一棵树，显然只要选定了起点，然后每次遍历子树时从小到大遍历即可。由于字典序要小，所以从 1 开始，一次 DFS 就能解决。

时间复杂度 $\mathcal{O}(n\log n)$ .（因为要排序）

40pts 基环树

仔细想想就会发现，由于 不是后退就是新点 ，所以易知无论图长什么样，我们都只会遍历到 $n-1$ 条边。所以其实就算有 $n$ 条边也是有一条没用的。那不妨枚举删掉一条，然后就可以按照树的方法跑了。

复杂度是 $\mathcal{O}(n^2)$ （排序在初始化就可以做掉，没必要放进 DFS 里面去），大概是 $2e7$ 左右。如果觉得不稳可以加剪枝，如果当前已经比答案劣了直接退出。

注意：删边要保证连通性，只要判最后 vis 了几个点就好了，没必要再写个找环；写剪枝（和最优解比较）的时候，只要前面有一次比最优解优，那么后面都不用判了，这点要加个标记。

大常数选手写了太多STL，所以在 ACWing 上得吸氧……

C++ 之父：STL常数大是你编译器不行（

//Author: RingweEH
const int N=5010;
int n,m,pos=0,cnt=0,better;
bool vis[N];
vector<int> g[N],path,ans;
pair<int,int> edge[N];

void dfs( int u )
{
    if ( (!better) && (u>ans[cnt]) ) return;
    if ( !better && u<ans[cnt] ) better=1;
    vis[u]=1; path.push_back( u ); cnt++;
    for ( int i=0; i<g[u].size(); i++ )
    {
        int v=g[u][i];
        if ( vis[v] ) continue;
        if ( (u==edge[pos].first) && (v==edge[pos].second ) ) continue;
        if ( (v==edge[pos].first) && (u==edge[pos].second ) ) continue;
        dfs( v );
    }
}

int main()
{
freopen( "travel.in","r",stdin ); freopen( "travel.out","w",stdout );

    n=read(); m=read();
    edge[0].first=edge[0].second=-1;
    for ( int i=1,u,v; i<=m; i++ )
    {
        u=read(),v=read(),g[u].push_back( v ),g[v].push_back( u );
        edge[i].first=u; edge[i].second=v;
    }

    for ( int i=1; i<=n; i++ )
        sort( g[i].begin(),g[i].end() );
    for ( int i=1; i<=n; i++ )
        ans.push_back( 60000 );
    if ( m==n )
    {
        for ( int i=1; i<=m; i++ )
        {
            memset( vis,0,sizeof(vis) ); path.clear();
            pos=i; cnt=better=0; dfs( 1 );
            if ( cnt==n ) ans=path;
        }
    }
    else
    {
        dfs( 1 );
        if ( cnt==n ) ans=path;
    }

    for ( int i=0; i<ans.size(); i++ )
        printf( "%d ",ans[i] );

fclose( stdin ); fclose( stdout );
    return 0;
}