代码

// NOIP2018 旅行 加强版 (duck.ac 2002)
// Base ring tree / tree, greedy DFS from node 1 with a single "turn back" on the cycle.
// O(n + m) counting-sort adjacency + DuckInfo direct memory IO.
#include <sys/auxv.h>
#include <stdint.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>

#ifdef LOCAL
#include <stdio.h>
#endif

typedef unsigned int u32;
typedef unsigned long long u64;

struct DuckInfo {
  u64 abi_version;
  const char *stdin_ptr; u64 stdin_size;
  char *stdout_ptr; u64 stdout_limit; u64 stdout_size;
  char *stderr_ptr; u64 stderr_limit; u64 stderr_size;
  const char *IB_ptr; u64 IB_limit;
  char *OB_ptr; u64 OB_limit;
  u64 tsc_frequency;
} __attribute__((packed));

static const char *inp;
static const char *inp_end;
static char *outp;

#ifdef LOCAL
static char ibuf[1 << 22];
static char obuf[1 << 22];
#else
static char *stdout_base;
static u64 *stdout_size_ptr;
#endif

static inline void init_io(void) {
#ifdef LOCAL
    size_t n = fread(ibuf, 1, sizeof(ibuf), stdin);
    inp = ibuf; inp_end = ibuf + n;
    outp = obuf;
#else
    struct DuckInfo *di = (struct DuckInfo *)getauxval(0x6b637564);
    inp = di->stdin_ptr; inp_end = di->stdin_ptr + di->stdin_size;
    outp = di->stdout_ptr;
    stdout_base = di->stdout_ptr;
    stdout_size_ptr = &di->stdout_size;
#endif
}

static inline int rd(void) {
    int x = 0;
    while (inp < inp_end && (unsigned)(*inp - '0') > 9) inp++;
    while (inp < inp_end && (unsigned)(*inp - '0') <= 9) {
        x = x * 10 + (*inp - '0');
        inp++;
    }
    return x;
}

static inline void put_int(int x, char sep) {
    char tmp[8];
    int i = 0;
    do { tmp[i++] = (char)('0' + x % 10); x /= 10; } while (x);
    while (i) *outp++ = tmp[--i];
    *outp++ = sep;
}

int main(void) {
    init_io();
    int n = rd();
    int m = rd();

    if (n == 1) {
        put_int(1, '\n');
#ifdef LOCAL
        fwrite(obuf, 1, (size_t)(outp - obuf), stdout);
        return 0;
#else
        *stdout_size_ptr = (u64)(outp - stdout_base);
        __asm__ volatile("syscall" : : "a"(60), "D"(0) : "rcx", "r11", "memory");
#endif
    }

    int em = 2 * m;
    int *eu = (int *)malloc((size_t)em * sizeof(int));
    int *ev = (int *)malloc((size_t)em * sizeof(int));
    int *etu = (int *)malloc((size_t)em * sizeof(int));
    int *etv = (int *)malloc((size_t)em * sizeof(int));
    int *cnt = (int *)malloc((size_t)(n + 2) * sizeof(int));
    int *deg = (int *)malloc((size_t)(n + 1) * sizeof(int));
    int *start = (int *)malloc((size_t)(n + 2) * sizeof(int));
    int *deg2 = (int *)malloc((size_t)(n + 1) * sizeof(int));
    unsigned char *oncycle = (unsigned char *)malloc((size_t)(n + 1));
    unsigned char *vis = (unsigned char *)malloc((size_t)(n + 1));
    int *queue = (int *)malloc((size_t)(n + 1) * sizeof(int));
    int *sx = (int *)malloc((size_t)(n + 1) * sizeof(int));
    int *si = (int *)malloc((size_t)(n + 1) * sizeof(int));
    int *sn = (int *)malloc((size_t)(n + 1) * sizeof(int));

    memset(deg, 0, (size_t)(n + 1) * sizeof(int));
    for (int i = 0; i < m; i++) {
        int u = rd();
        int v = rd();
        eu[2 * i] = u; ev[2 * i] = v;
        eu[2 * i + 1] = v; ev[2 * i + 1] = u;
        deg[u]++; deg[v]++;
    }

    // counting sort directed edges by (to) then (from) => sorted adjacency lists
    memset(cnt, 0, (size_t)(n + 2) * sizeof(int));
    for (int i = 0; i < em; i++) cnt[ev[i]]++;
    for (int i = 1; i <= n; i++) cnt[i] += cnt[i - 1];
    for (int i = em - 1; i >= 0; i--) {
        int c = --cnt[ev[i]];
        etu[c] = eu[i]; etv[c] = ev[i];
    }
    memset(cnt, 0, (size_t)(n + 2) * sizeof(int));
    for (int i = 0; i < em; i++) cnt[etu[i]]++;
    for (int i = 1; i <= n; i++) cnt[i] += cnt[i - 1];
    for (int i = em - 1; i >= 0; i--) {
        int c = --cnt[etu[i]];
        eu[c] = etu[i]; ev[c] = etv[i];
    }

    start[1] = 0;
    for (int i = 1; i <= n; i++) start[i + 1] = start[i] + deg[i];

    // degree peeling to find cycle nodes
    memcpy(deg2, deg, (size_t)(n + 1) * sizeof(int));
    memset(oncycle, 1, (size_t)(n + 1));
    int qh = 0, qt = 0;
    for (int i = 1; i <= n; i++) if (deg2[i] <= 1) queue[qt++] = i;
    while (qh < qt) {
        int u = queue[qh++];
        if (!oncycle[u]) continue;
        oncycle[u] = 0;
        int s = start[u], e = start[u] + deg[u];
        for (int k = s; k < e; k++) {
            int v = ev[k];
            if (oncycle[v]) {
                if (--deg2[v] == 1) queue[qt++] = v;
            }
        }
    }

    // greedy DFS with at-most-one turn-back
    memset(vis, 0, (size_t)(n + 1));
    vis[1] = 1;
    put_int(1, ' ');
    int top = 0;
    sx[top] = 1; si[top] = start[1]; sn[top] = 0x7fffffff; top++;
    int turned = 0;
    while (top > 0) {
        int x = sx[top - 1];
        int idx = si[top - 1];
        int now = sn[top - 1];
        int e = start[x] + deg[x];
        while (idx < e && vis[ev[idx]]) idx++;
        if (idx >= e) { top--; continue; }
        int tt = ev[idx];
        int j = idx + 1;
        while (j < e && vis[ev[j]]) j++;
        int has_next = (j < e);
        int next_val = has_next ? ev[j] : 0;
        if (!turned && oncycle[tt] && !has_next && now < tt) {
            turned = 1;
            top--;
            continue;
        }
        vis[tt] = 1;
        put_int(tt, ' ');
        si[top - 1] = j;
        int child_now = (oncycle[x] && has_next) ? next_val : now;
        sx[top] = tt; si[top] = start[tt]; sn[top] = child_now;
        top++;
    }

    outp[-1] = '\n';
#ifdef LOCAL
    fwrite(obuf, 1, (size_t)(outp - obuf), stdout);
    fflush(stdout);
    return 0;
#else
    *stdout_size_ptr = (u64)(outp - stdout_base);
    __asm__ volatile("syscall" : : "a"(60), "D"(0) : "rcx", "r11", "memory");
    __builtin_unreachable();
#endif
}

评测结果