代码

// 2002 travel (see notes)
// 2002 【NOIP2018】旅行（加强版） — O(n+m) with online cut decision.
//
// For a base-ring tree the optimal travel = greedy sorted DFS of T minus one
// cycle edge.  While walking the cycle in the first-chosen direction, at the
// moment the DFS wants to step onto the forward cycle edge (u->v), cutting that
// edge yields next node M = the deepest pending child on the DFS stack, while
// continuing yields v.  All candidates that continue share v at that position,
// so cut iff M < v (labels are distinct).  That decision is final.
#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 visited[MAXN], visStamp = 1;
static unsigned char isCyc[MAXN];
static int fbn[MAXN];
static int stkNode[MAXN], stkPtr[MAXN], nxtPtr[MAXN], deepBelow[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;
    for (int i = 1; i <= n; i++) deg[i] = start_[i];
    for (int i = 0; i < m; i++) {
        adj[deg[eu[i]]++] = ev[i];
        adj[deg[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]);
    }
}

static inline int nextUnv(int lvl) {
    int u = stkNode[lvl];
    int i = nxtPtr[lvl], e = start_[u + 1], fb = fbn[u];
    while (i < e) { int w = adj[i]; if (visited[w] != visStamp && w != fb) break; i++; }
    nxtPtr[lvl] = i;
    return i < e ? i : -1;
}

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++;
        if (p + 8 <= pend) {
            u64 x;
            __builtin_memcpy(&x, p, 8);
            u64 bad = ((x ^ 0x3030303030303030ULL) + 0x7676767676767676ULL)
                      & 0x8080808080808080ULL;
            int k = bad ? (int)(__builtin_ctzll(bad) >> 3) : 8;
            int sh = 8 * (8 - k);
            u64 xx = (x << sh) | (0x3030303030303030ULL & ((sh == 64) ? 0ULL : ((1ULL << sh) - 1ULL)));
            u64 d = xx - 0x3030303030303030ULL;
            u64 t = (d * 10 + (d >> 8)) & 0x00FF00FF00FF00FFULL;
            t = (t * 100 + (t >> 16)) & 0x0000FFFF0000FFFFULL;
            t = (t * 10000 + (t >> 32)) & 0xFFFFFFFFULL;
            p += k;
            return (int)(unsigned)t;
        }
        unsigned v = 0;
        while (p < pend && *p >= '0' && *p <= '9') v = v * 10 + (unsigned)(*p++ - '0');
        return (int)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));
    memset(isCyc, 0, (size_t)(n + 2));

    if (m == n) {
        int *d2 = deg, *queue_ = stkNode;
        for (int i = 1; i <= n; i++) d2[i] = start_[i + 1] - start_[i];
        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;
        }
        for (int i = 1; i <= n; i++) if (d2[i] > 1) isCyc[i] = 1;
    }

    // greedy DFS with online cut decision; output emitted on the fly
    static char D4[10000][4];
    for (int i = 0; i < 10000; i++) {
        D4[i][0] = (char)('0' + i / 1000);
        D4[i][1] = (char)('0' + (i / 100) % 10);
        D4[i][2] = (char)('0' + (i / 10) % 10);
        D4[i][3] = (char)('0' + i % 10);
    }
    char *o = OUT;
    auto emit = [&](int v) {
        if (v >= 10000) {
            int hi = v / 10000, lo = v - hi * 10000;
            if (hi >= 10) { *o++ = (char)('0' + hi / 10); *o++ = (char)('0' + hi % 10); }
            else *o++ = (char)('0' + hi);
            __builtin_memcpy(o, D4[lo], 4); o += 4;
        } else if (v >= 100) {
            int hi = v / 100, lo = v - hi * 100;
            if (hi >= 10) { *o++ = (char)('0' + hi / 10); *o++ = (char)('0' + hi % 10); }
            else *o++ = (char)('0' + hi);
            *o++ = (char)('0' + lo / 10); *o++ = (char)('0' + lo % 10);
        } else if (v >= 10) {
            *o++ = (char)('0' + v / 10); *o++ = (char)('0' + v % 10);
        } else *o++ = (char)('0' + v);
        *o++ = ' ';
    };
    int sp = 0, cutMade = 0;
    ++visStamp;
    visited[1] = visStamp; emit(1);
    stkNode[0] = 1; stkPtr[0] = start_[1]; nxtPtr[0] = start_[1]; deepBelow[0] = -1;
    while (sp >= 0) {
        int u = stkNode[sp];
        int i = nextUnv(sp);
        if (i < 0) { sp--; continue; }
        int v = adj[i];
        if (!cutMade && isCyc[u] && isCyc[v]) {
            int save = nxtPtr[sp];
            nxtPtr[sp] = i + 1;
            int j = nextUnv(sp);
            nxtPtr[sp] = save;
            if (j < 0) {
                int d = deepBelow[sp];
                if (d >= 0) {
                    int mi = nextUnv(d);
                    if (mi >= 0 && adj[mi] < v) {
                        fbn[u] = v; fbn[v] = u; cutMade = 1;
                        continue;
                    }
                }
            }
        }
        stkPtr[sp] = i + 1; nxtPtr[sp] = i + 1;
        visited[v] = visStamp; emit(v);
        sp++;
        stkNode[sp] = v; stkPtr[sp] = start_[v]; nxtPtr[sp] = start_[v];
        int pr = nextUnv(sp - 1);
        deepBelow[sp] = (pr >= 0) ? sp - 1 : deepBelow[sp - 1];
    }

    *(o - 1) = '\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;
}

评测结果