记录编号	585889	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2018]旅行	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	1.908 s
提交时间	2023-12-27 19:16:51	内存使用	1.29 MiB

#include <bits/stdc++.h>
using namespace std;
#define long long
const int N = 1e4+10;
int n,m;
struct made{
    int ver,nx;
}e[N<<2];
int hd[N],tot,v[N],ve[N],cnt;
int ans[N],s[N];
void add(int x,int y){
    tot++;
    e[tot].nx = hd[x],e[tot].ver = y,hd[x] = tot;
}
bool find(int x,int fa){
    if(v[x] == 1){v[x] = 2;return 1;}
    v[x] = 1;
    for(int i = hd[x];i;i = e[i].nx){
        int y = e[i].ver;
        if(y == fa)continue;
        if(find(y,x)){
            ve[i] = ve[i^1] = 2;
            if(v[x] == 2)return 0;
            v[x] = 2;
            return 1;
        }
    }
    return 0;
}
bool f;
void dfs(int x,int fa){
    s[++cnt] = x;
    if(s[cnt] < ans[cnt])f = 1;
    if(s[cnt] > ans[cnt] && !f)return;
    vector<int>son;
    for(int i = hd[x];i;i = e[i].nx){
        int y = e[i].ver;
        if(y == fa || v[i])continue;
        son.push_back(y);
    }
    sort(son.begin(),son.end());
    for(int i = 0;i < son.size();i++)dfs(son[i],x);
} 
bool check(){
    for(int i = 1;i <= n;i++){
        if(s[i] == 0)return 0;
        if(ans[i] > s[i])return 1;
        if(ans[i] < s[i])return 0;
    }
    return 0;
}
int main(){
    freopen("2018travel.in","r",stdin);
    freopen("2018travel.out","w",stdout);
    scanf("%d%d",&n,&m);
    tot = 1;
    for(int i = 1;i <= m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
    }
    memset(ans,0x3f,sizeof(ans));
    if(m == n-1){
        dfs(1,0);
        for(int i = 1;i <= n;i++)printf("%d ",s[i]);
        printf("\n");
        return 0;
    }
    find(1,0);
    memset(v,0,sizeof(v));
    for(int i = 2;i <= 2*n;i+=2){
        if(ve[i] == 2){
            v[i] = v[i^1] = 1;
            cnt = 0;f = 0;
            dfs(1,0);
            if(check())memcpy(ans,s,sizeof(s));
            v[i] = v[i^1] = 0;
        }
    }
    for(int i = 1;i <= n;i++)printf("%d ",ans[i]);
    printf("\n");
    
    return 0;
    
}