代码

// 2002 【NOIP2018】旅行（加强版）
// n <= 500000, m = n-1 (tree) or m = n (base ring tree).
// Lexicographically smallest DFS order; self-written grep DFS with early abort
// over the ring-edge candidates.  Direct DuckInfo stdin/stdout.
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>

typedef unsigned long long u64;

#ifdef TEST_IO
static const char *IN; static u64 INSZ; static char *OUT; static u64 OUTSZ = 0; static u64 OUTLIM = 1u << 28;
#else
struct DI { u64 abi; const char*in; u64 insz; char*out; u64 outlim; u64 outsz; char*err;
            u64 errlim; u64 errsz; const char*IB; u64 IBlim; char*OB; u64 OBlim; u64 tscfreq; }
            __attribute__((packed));
#define DUCKINFO 0x243FFF90ULL
static struct DI *di;
static const char *IN; static u64 INSZ; static char *OUT; static u64 OUTSZ = 0; static u64 OUTLIM;
#endif

static const int MAXN = 500005;
static int n, m;
static int eu[MAXN], ev[MAXN];
static int start_[MAXN + 1], adj[2 * MAXN];
static int deg[MAXN];
static int seq[MAXN], bestSeq[MAXN];
static int visited[MAXN], visStamp = 1;
static int fbn[MAXN];                 // forbidden neighbour for the cut edge
static int stkNode[MAXN], stkIdx[MAXN];

static inline void buildGraph() {
    for (int i = 1; i <= n; i++) deg[i] = 0;
    for (int i = 0; i < m; i++) { deg[eu[i]]++; deg[ev[i]]++; }
    int s = 0;
    for (int i = 1; i <= n; i++) { start_[i] = s; s += deg[i]; }
    start_[n + 1] = s;
    static int pos[MAXN];
    for (int i = 1; i <= n; i++) pos[i] = start_[i];
    for (int i = 0; i < m; i++) {
        adj[pos[eu[i]]++] = ev[i];
        adj[pos[ev[i]]++] = eu[i];
    }
    for (int i = 1; i <= n; i++) {
        int d = start_[i + 1] - start_[i];
        if (d <= 1) continue;
        if (d <= 24) {
            for (int a = start_[i] + 1; a < start_[i + 1]; a++) {
                int x = adj[a], b = a - 1;
                while (b >= start_[i] && adj[b] > x) { adj[b + 1] = adj[b]; b--; }
                adj[b + 1] = x;
            }
        } else std::sort(adj + start_[i], adj + start_[i + 1]);
    }
}

// Simulate greedy DFS avoiding edge (a,b).  Writes into out[]; compares against
// best[] incrementally.  Returns 1 if strictly better (out holds the winner),
// 0 otherwise (aborted or equal).
static int simulate(int a, int b, int *out, const int *best_, int bestLen) {
    fbn[a] = b; fbn[b] = a;
    ++visStamp;
    int len = 0, sp = 0;
    visited[1] = visStamp;
    out[len++] = 1;
    int cmp = 0;                       // -1 better, 0 equal so far
    if (bestLen == 0) cmp = -1;
    else if (out[0] < best_[0]) cmp = -1;
    else if (out[0] > best_[0]) { fbn[a] = fbn[b] = -1; return 0; }
    stkNode[0] = 1; stkIdx[0] = start_[1];
    while (sp >= 0) {
        int u = stkNode[sp];
        int i = stkIdx[sp];
        int e = start_[u + 1];
        int v = -1;
        while (i < e) {
            int w = adj[i];
            if (visited[w] != visStamp && w != fbn[u]) { v = w; break; }
            i++;
        }
        if (v >= 0) {
            stkIdx[sp] = i + 1;
            visited[v] = visStamp;
            out[len] = v;
            if (cmp == 0) {
                if (len >= bestLen) cmp = 1;             // longer than best => worse
                else if (v < best_[len]) cmp = -1;
                else if (v > best_[len]) { fbn[a] = fbn[b] = -1; return 0; }
            }
            len++;
            stkNode[++sp] = v; stkIdx[sp] = start_[v];
        } else {
            stkIdx[sp] = i;
            sp--;
        }
    }
    fbn[a] = fbn[b] = -1;
    return cmp < 0 ? 1 : 0;
}

int main() {
#ifdef TEST_IO
    static char inbuf[1 << 26];
    INSZ = fread(inbuf, 1, sizeof(inbuf), stdin);
    IN = inbuf;
    static char outbuf[1 << 25];
    OUT = outbuf; OUTLIM = sizeof(outbuf);
#else
    di = (struct DI *)DUCKINFO;
    IN = di->in; INSZ = di->insz;
    OUT = di->out; OUTLIM = di->outlim;
#endif
    const char *p = IN, *pend = IN + INSZ;
    auto readInt = [&]() -> int {
        while (p < pend && (*p < '0' || *p > '9')) p++;
        int v = 0;
        while (p < pend && *p >= '0' && *p <= '9') v = v * 10 + (*p++ - '0');
        return v;
    };
    n = readInt(); m = readInt();
    for (int i = 0; i < m; i++) { eu[i] = readInt(); ev[i] = readInt(); }
    buildGraph();
    memset(fbn, -1, sizeof(int) * (n + 2));

    int bestLen = 0;
    if (m == n - 1) {
        if (simulate(0, 0, bestSeq, bestSeq, 0)) bestLen = n;
    } else {
        // peel leaves to find the cycle
        static int d2[MAXN];
        for (int i = 1; i <= n; i++) d2[i] = start_[i + 1] - start_[i];
        static int queue_[MAXN];
        int qh = 0, qt = 0;
        for (int i = 1; i <= n; i++) if (d2[i] == 1) queue_[qt++] = i;
        while (qh < qt) {
            int u = queue_[qh++];
            for (int i = start_[u]; i < start_[u + 1]; i++) {
                int v = adj[i];
                if (d2[v] > 1) { if (--d2[v] == 1) queue_[qt++] = v; }
            }
            d2[u] = 0;
        }
        static int cyc[MAXN];
        int L = 0;
        for (int i = 1; i <= n; i++) if (d2[i] > 1) cyc[L++] = i;
        // order cycle
        static int ordered[MAXN];
        int olen = 0;
        int cur = cyc[0], prev = 0;
        do {
            ordered[olen++] = cur;
            int nxt = 0;
            for (int i = start_[cur]; i < start_[cur + 1]; i++) {
                int v = adj[i];
                if (d2[v] > 1 && v != prev) { nxt = v; break; }
            }
            prev = cur; cur = nxt;
        } while (cur && olen < L);
        L = olen;
        for (int k = 0; k < L; k++) {
            int a = ordered[k], b = ordered[(k + 1) % L];
            if (simulate(a, b, seq, bestSeq, bestLen)) {
                memcpy(bestSeq, seq, sizeof(int) * n);
                bestLen = n;
            }
        }
    }
    // output
    char *o = OUT;
    for (int i = 0; i < n; i++) {
        int v = bestSeq[i];
        char tmp[12];
        int k = 0;
        do { tmp[k++] = (char)('0' + v % 10); v /= 10; } while (v);
        while (k) *o++ = tmp[--k];
        *o++ = (i + 1 == n) ? '\n' : ' ';
    }
    OUTSZ = (u64)(o - OUT);
#ifdef TEST_IO
    fwrite(outbuf, 1, OUTSZ, stdout);
#else
    di->outsz = OUTSZ;
    register long rax __asm__("rax") = 60;
    register long rdi __asm__("rdi") = 0;
    __asm__ volatile("syscall" :: "a"(rax), "D"(rdi) : "rcx", "r11", "memory");
    __builtin_unreachable();
#endif
    return 0;
}

评测结果