NOIP2018D2T1 旅行

#include<cstdio>
#include<set>
#include<cstring>

int n,m,cnt,mini[500005],ans[500005],u[500005],v[500005];

bool vis[500005];

std::set<int> e[500005];

inline bool cmp(const int *a,const int *b,int now){
    for(int i=1;i<=now;i++){
        if(a[i]<b[i])return true;
        if(a[i]>b[i])return false;
    }
    return true;
}

inline void dfs(int u){
    vis[u]=1;
    ans[++cnt]=u;
    if(!cmp(ans,mini,cnt))return;
    if(cnt==n){
        for(int i=1;i<=n;i++)mini[i]=ans[i];
    }
    for(std::set<int>::iterator it=e[u].begin();it!=e[u].end();it++){
        int v=*it;
        if(!vis[v]){
            dfs(v);
        }
    }
}

int main(){
    memset(mini,0x3f,sizeof(mini));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&u[i],&v[i]);
        e[u[i]].insert(v[i]);
        e[v[i]].insert(u[i]);
    }
    if(n==m){
        for(int i=1;i<=m;i++){
            if(i>1){
                e[u[i-1]].insert(v[i-1]);
                e[v[i-1]].insert(u[i-1]);
            }
            e[u[i]].erase(v[i]);
            e[v[i]].erase(u[i]);
            cnt=0;
            memset(vis,0,sizeof(vis));
            vis[1]=1;
            dfs(1);
        }
    }
    else{
        dfs(1);
    }
    for(int i=1;i<=n;i++){
        printf("%d ",mini[i]);
    }   
}

NOIP2018D2T1 旅行

原文：https://www.cnblogs.com/Y15BeTa/p/11570086.html