题目描述

小 Y 是一个爱好旅行的 OIer。她来到 X 国，打算将各个城市都玩一遍。
小 Y 了解到，X 国的 𝑛 个城市之间有 𝑚 条双向道路。每条双向道路连接两个城市。 不存在两条连接同一对城市的道路，也不存在一条连接一个城市和它本身的道路。并且， 从任意一个城市出发，通过这些道路都可以到达任意一个其他城市。小 Y 只能通过这些 道路从一个城市前往另一个城市。
小 Y 的旅行方案是这样的:任意选定一个城市作为起点，然后从起点开始，每次可 以选择一条与当前城市相连的道路，走向一个没有去过的城市，或者沿着第一次访问该 城市时经过的道路后退到上一个城市。当小 Y 回到起点时，她可以选择结束这次旅行或 继续旅行。需要注意的是，小 Y 要求在旅行方案中，每个城市都被访问到。
为了让自己的旅行更有意义，小 Y 决定在每到达一个新的城市(包括起点)时，将 它的编号记录下来。她知道这样会形成一个长度为 𝑛 的序列。她希望这个序列的字典序 最小，你能帮帮她吗?
对于两个长度均为 𝑛 的序列 A 和 B，当且仅当存在一个正整数 x，满足以下条件时， 我们说序列 A 的字典序小于 B。
1.对于任意正整数1≤i<x，序列A的第i个元素Ai 和序列B的第i个元素 Bi 相同。
2. 序列A的第 x 个元素的值小于序列B的第 x 个元素的值。

输入描述:

输入文件共 𝑚 + 1 行。第一行包含两个整数 𝑛, 𝑚(𝑚 ≤ 𝑛) ，中间用一个空格分隔。
接下来 𝑚 行，每行包含两个整数 𝑢, 𝑣 (1 ≤ 𝑢, 𝑣 ≤ 𝑛) ，表示编号为 𝑢 和 𝑣 的城市之 间有一条道路，两个整数之间用一个空格分隔。

输出描述:

输出文件包含一行， 𝑛 个整数，表示字典序最小的序列。相邻两个整数之间用一个 空格分隔。

示例1

输入
6 5
1 3
2 3
2 5
3 4
4 6
输出
1 3 2 5 4 6

示例2

输入
6 6
1 3
2 3
2 5
3 4
4 5
4 6
输出
1 3 2 4 5 6

备注

对于 100% 的数据和所有样例，1 ≤ 𝑛 ≤ 5000 且 𝑚 = 𝑛 − 1 或 𝑚 = 𝑛 。 对于不同的测试点，我们约定数据的规模如下:

解答

乍一看，一道基环树。
说实话考场上有点懵，Day2T1直接上基环树？
再一看，好像只是一道无脑的搜索加剪枝
对于NOIP数据范围，是可以可过去的
但是对于那个加强版数据，可能需要一个笔者不会的超级玄学。
好吧不扯了，咱们来看看数据范围。
m=n-1的情况比较简单只需一遍跑一边搜索，每次找字典序最小的往下搜就行了。
而对于m=n的情况，就是神（wei）奇（suo）的基环树了。
对于基环树的简单定义，可以说是一颗有且仅有一个简单环的树，再通俗一点，就是一个n个点n条边的连通图。
但是，其实用不着基环树的知识
终极奥秘，暴力
没错，只要暴力删除任意一条边就行了，再跑搜索。
因为总有一条边是用不到的。
最后加一个剪枝，就是如果当前搜到的字典序肯定大于搜到过的答案了，那就return掉
直接上代码
#include<bits/stdc++.h>

using namespace std;

int n,m;
vector<int> edge[10010];
int d1,d2,d3,d4;
vector<int> ans1,ans2;
bool ha[5010][5010];
int cnt;
bool h,k;

template <typename T> inline void read(T &x){
    T f=1; x=0; char c=getchar();
    for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
    for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);
    x*=f;
}

inline void addedge(int u,int v){
    edge[u].push_back(v);
    edge[v].push_back(u);
}

inline bool chck(int u,int v){
    return (u==d1&&v==d2)||(u==d3&&v==d4);
}

void dfs(int u){
    if(!h)return;
    ans2.push_back(u);
    if(!k&&ans1.size()>0&&ans2[ans2.size()-1]>ans1[ans2.size()-1]){h=0;return;}
    if(ans1.size()>0&&ans2[ans2.size()-1]<ans1[ans2.size()-1])k=1;
    ha[u][cnt]=1;
    for(int i=0;i<edge[u].size();i++){
        int v=edge[u][i];
        if(ha[v][cnt]||chck(u,v))continue;
        dfs(v);
    }
}

inline void print(){
    for(int i=0;i<n-1;i++)printf("%d ",ans1[i]);
    printf("%d\n",ans1[n-1]);
}

int main(){
    
    read(n);read(m);
    for(int i=1;i<=m;i++){
        int u,v;
        read(u);read(v);
        addedge(u,v);
    }
    
    for(int i=1;i<=n;i++)sort(edge[i].begin(),edge[i].end());
    
    if(m==n-1){
        h=1;
        dfs(1);
        ans1=ans2;
        print();
        return 0;
    }

    for(int i=1;i<=n;i++){
        for(int j=0;j<edge[i].size();j++){
            cnt++;
            d1=d4=edge[i][j];
            d2=d3=i;
            ans2.clear();
            h=1;
            k=0;
            dfs(1);	
            if(!h)continue;
            if(ans2.size()<n)continue;
            ans1=ans2;
        }
    }
    
    print();
    
    return 0;
}


来源：cz_wangjunpeng