代码

// NOIP2018 旅行 (noip18d), fast version.
// m = n-1 : greedy DFS on the tree.
// m = n   : unique cycle; the optimal walk = DFS of the tree obtained by
//           deleting one cycle edge.  All cycle edges are considered in O(k)
//           via a local-divergence scan (see notes), plus the special
//           "counter-clockwise only" candidate.
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
typedef vector<int> vi;
static const int INFV = 0x3f3f3f3f;

static int N, M;
static vi eu, ev;
static vector<vi> adj;
static vi csrStart, csrTo;

static void buildCSR(){
    csrStart.assign(N+2, 0);
    for(int i=1;i<=N;i++) csrStart[i+1] = (int)adj[i].size();
    for(int i=1;i<=N;i++) csrStart[i+1] += csrStart[i];
    csrTo.assign(M*2, 0);
    vi pos(csrStart.begin(), csrStart.end());
    for(int i=1;i<=N;i++) for(size_t j=0;j<adj[i].size();j++) csrTo[pos[i]++] = adj[i][j];
}

static void genSeq(int bu, int bv, vector<int>& out){
    out.clear();
    static vector<char> vis; vis.assign(N+1, 0);
    static vi stkU, stkI;
    stkU.clear(); stkI.clear();
    out.push_back(1); vis[1]=1;
    stkU.push_back(1); stkI.push_back(csrStart[1]);
    while(!stkU.empty()){
        int u = stkU.back();
        int &i = stkI.back();
        int adv = 0;
        int end = csrStart[u+1];
        while(i < end){
            int v = csrTo[i++];
            if(vis[v]) continue;
            if((u==bu && v==bv) || (u==bv && v==bu)) continue;
            vis[v]=1; out.push_back(v);
            stkU.push_back(v); stkI.push_back(csrStart[v]); adv=1; break;
        }
        if(!adv){ stkU.pop_back(); stkI.pop_back(); }
    }
}

// returns the answer sequence
static void fast_solve_case(int n, int m, const vi& A, const vi& B, vector<int>& out){
    N=n; M=m; eu=A; ev=B;
    adj.assign(N+1, vi());
    for(int i=0;i<M;i++){ adj[A[i]].push_back(B[i]); adj[B[i]].push_back(A[i]); }
    for(int i=1;i<=N;i++) sort(adj[i].begin(), adj[i].end());
    buildCSR();
    if(M == N-1){ genSeq(-1,-1,out); return; }
    // ---- find cycle nodes by peeling degree-1 vertices ----
    static vi deg; deg.assign(N+1,0); static vector<char> rem; rem.assign(N+1,0);
    static vi q; q.clear();
    for(int i=1;i<=N;i++){ deg[i]=(int)adj[i].size(); }
    for(int i=1;i<=N;i++) if(deg[i]==1) q.push_back(i);
    size_t qh=0;
    while(qh<q.size()){
        int u=q[qh++]; rem[u]=1;
        for(size_t j=0;j<adj[u].size();j++){ int v=adj[u][j]; if(!rem[v] && --deg[v]==1) q.push_back(v); }
    }
    // ---- r = first ring node on the (unique) path from 1 (BFS) ----
    static vi par; par.assign(N+1,0);
    static vi bq; bq.clear();
    static vector<char> seen; seen.assign(N+1,0);
    seen[1]=1; bq.push_back(1); par[1]=0;
    int r=0;
    for(size_t i=0;i<bq.size() && !r;i++){
        int u=bq[i];
        if(!rem[u]){ r=u; break; }
        for(size_t j=0;j<adj[u].size();j++){ int v=adj[u][j]; if(!seen[v]){ seen[v]=1; par[v]=u; bq.push_back(v); } }
    }
    if(!r) r=1;
    // ---- order the ring from r ----
    vi ring; ring.push_back(r);
    {
        int prev=r, cur=-1;
        for(size_t j=0;j<adj[r].size();j++) if(!rem[adj[r][j]]){ cur=adj[r][j]; break; }
        while(cur!=-1 && cur!=r){
            ring.push_back(cur);
            int nxt=-1;
            for(size_t j=0;j<adj[cur].size();j++){ int v=adj[cur][j]; if(!rem[v] && v!=prev){ nxt=v; break; } }
            prev=cur; cur=nxt;
        }
    }
    int k=(int)ring.size();
    if(k>=3 && ring[1] > ring[k-1]){
        reverse(ring.begin()+1, ring.end());
    }
    vi a = ring;
    static vi ringIdx; ringIdx.assign(N+1,-1);
    for(int i=0;i<k;i++) ringIdx[a[i]]=i;
    // ---- hanging subtree roots ----
    vector<vi> hs(k);
    for(int i=0;i<k;i++){
        int u=a[i];
        for(size_t j=0;j<adj[u].size();j++){
            int v=adj[u][j];
            if(ringIdx[v]>=0) continue;
            if(u==r && v==par[r]) continue;   // path parent: already visited
            hs[i].push_back(v);
        }
    }
    // ---- W[i] = min(H_i > a[i+1]) (i=1..k-2), unwindPrev, NEXT_R ----
    static vi W; W.assign(k, INFV);
    for(int i=1;i+1<k;i++){
        vi& h=hs[i];
        vi::iterator it = upper_bound(h.begin(), h.end(), a[i+1]);
        if(it!=h.end()) W[i]=*it;
    }
    static vi unw; unw.assign(k, INFV);
    {
        int last=INFV;
        for(int i=1;i+1<k;i++){
            if(W[i]<INFV) last=W[i];
            unw[i+1]=last;
        }
    }
    int nextR = INFV;
    {
        vi& h=hs[0];
        vi::iterator it = upper_bound(h.begin(), h.end(), a[1]);
        if(it!=h.end()) nextR=*it;
        if(a[k-1] < nextR) nextR=a[k-1];
    }
    int best = k-1;
    for(int j=k-2;j>=1;j--){
        int vj;
        if(W[j]<INFV) vj=W[j];
        else if(unw[j]<INFV) vj=unw[j];
        else vj=nextR;
        if(vj < a[j+1]) best=j;
    }
    vector<int> s1, s0;
    if(best==k-1) genSeq(a[k-1], a[0], s1);
    else genSeq(a[best], a[best+1], s1);
    genSeq(a[0], a[1], s0);
    out.clear(); out.reserve(N);
    const vector<int>& win = (s0 < s1) ? s0 : s1;
    out = win;
}

#ifdef FUZZ
#define MAIN_NAME fuzz_main_unused
#else
#define MAIN_NAME main
#endif

int MAIN_NAME(){
    int n,m;
    if(scanf("%d %d",&n,&m)!=2) return 0;
    eu.resize(m); ev.resize(m);
    for(int i=0;i<m;i++){ scanf("%d %d",&eu[i],&ev[i]); }
    vector<int> res;
    fast_solve_case(n,m,eu,ev,res);
    // output
    {
        size_t cap = (size_t)n*8 + 16;
        static vector<char> buf;
        buf.resize(cap);
        size_t p=0;
        for(int i=0;i<(int)res.size();i++){
            int x=res[i];
            char t[12]; int tk=0;
            if(x==0) t[tk++]='0';
            while(x){ t[tk++]='0'+x%10; x/=10; }
            while(tk) buf[p++]=t[--tk];
            buf[p++] = (i+1<(int)res.size()) ? ' ' : '\n';
            if(p+16>cap){ buf.resize(cap*2); cap*=2; }
        }
        fwrite(buf.data(),1,p,stdout);
    }
    return 0;
}

评测结果