题解 P5022 【旅行】

Ganshuaige · 2018-11-16 21:30:09 · 题解

Noip 2018 Day2 T1

暴力删边n^2

没错就是这样

那一个E数组存u，v。

再用一个vector排序

#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<algorithm>

const int Maxn = 5005;
using namespace std;

int cnt;
int head[Maxn];
struct edge{
    int u,v,next;
}e[Maxn<<1];

void adde(int u,int v){
    e[cnt].u=u;
    e[cnt].v=v;
    e[cnt].next=head[u];
    head[u]=cnt++;
}

vector <int> vec[Maxn];

int n,m;
int ans[Maxn];
int k[Maxn];

int x,y;
int dep;
bool vis[Maxn];

void dfs(int u,int fa){
    if(vis[u])
        return;
    vis[u]=1;
    k[++dep]=u;
    for(int i=0;i<vec[u].size();i++){
        int v=vec[u][i];
        if(v==fa)
            continue;
        if((v==y&&u==x)||(v==x&&u==y))
            continue;
        dfs(v,u);
    }
}

bool check(){
    for(int i=1;i<=n;i++){
        if(k[i]==ans[i])
            continue;
        if(k[i]>ans[i])
            return false;
        else
            return true;
    }
}

void change(){
    for(int i=1;i<=n;i++)
        ans[i]=k[i];
}

//Finally u can know China Computer Federation
void fuckccf(int u,int fa){
    if(vis[u])
        return;
    vis[u]=1;
    ans[++dep]=u;
    for(int i=0;i<vec[u].size();i++){
        int v=vec[u][i];
        if(v==fa)
            continue;
        fuckccf(v,u);
    }
}

int main(){
    int u,v;
    memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        vec[u].push_back(v);
        vec[v].push_back(u);
        adde(u,v);
        adde(v,u);
    }
    for(int i=1;i<=n;i++)
        sort(vec[i].begin(),vec[i].end());
    if(n==m){
        for(int i=0;i<cnt;i+=2){
            dep=0;x=e[i].u;y=e[i].v;
            memset(vis,0,sizeof(vis));
            dfs(1,-1);
            if(dep<n)
                continue;
            if(ans[1]==0)
                change();
            else if(check()) change();
        }                    
        for(int i=1;i<=n;i++)
            printf("%d ",ans[i]);
        return 0;
    }
    fuckccf(1,-1);
    for(int i=1;i<=n;i++)
        printf("%d ",ans[i]);
    return 0;
}