代码

// This code is AI-generated. (AI 生成的代码)
// NOIP2018 旅行.  Build CSR adjacency, sort each node's neighbours, then if m==n
// peel degree-1 vertices to find the cycle.  A greedy iterative DFS visits the
// smallest unvisited neighbour; when it reaches a cycle vertex whose two cycle
// neighbours are ordered badly it skips one branch once (the "turn"), which is
// the only case where the naive greedy is not optimal.
#include <sys/auxv.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>

typedef unsigned 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 char *outp;
static char D2[] = "00010203040506070809101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899";

static inline int rd() {
    const char *p = inp;
    while (*p < '0') ++p;
    int x = 0;
    do { x = x * 10 + (*p - '0'); ++p; } while (*p >= '0');
    inp = p;
    return x;
}
static inline void put_int(int x, char sep) {
    char t[8];
    char *p = t;
    do { int r = x % 100; x /= 100; *p++ = D2[r * 2 + 1]; *p++ = D2[r * 2]; } while (x > 0);
    if (p[-1] == '0') --p;
    while (p > t) *outp++ = *--p;
    *outp++ = sep;
}

#ifdef LOCAL
#include <stdio.h>
static char lib[1 << 25], lob[1 << 25];
static struct DuckInfo ldi;
#endif
int main() {
    struct DuckInfo *di = (struct DuckInfo *)getauxval(0x6b637564UL);
#ifdef LOCAL
    if (!di) { int z = (int)fread(lib, 1, sizeof(lib) - 1, stdin); lib[z] = 0; ldi.stdin_ptr = lib; ldi.stdout_ptr = lob; di = &ldi; }
#endif
    inp = di->stdin_ptr;
    outp = di->stdout_ptr;

    int n = rd(), m = rd();
    int em = 2 * m;
    int *eu = (int *)malloc((size_t)em * sizeof(int));
    int *ev = (int *)malloc((size_t)em * sizeof(int));
    int *csr = (int *)malloc((size_t)em * sizeof(int));
    int *cur = (int *)malloc((size_t)(n + 1) * 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(), v = rd();
        eu[2 * i] = u; ev[2 * i] = v;
        eu[2 * i + 1] = v; ev[2 * i + 1] = u;
        deg[u]++; deg[v]++;
    }
    start[1] = 0;
    for (int i = 1; i <= n; i++) start[i + 1] = start[i] + deg[i];
    memcpy(cur, start, (size_t)(n + 1) * sizeof(int));
    for (int i = 0; i < em; i++) { int u = eu[i]; csr[cur[u]++] = ev[i]; }
    for (int i = 1; i <= n; i++) {
        int s = start[i], d = deg[i], e = s + d;
        if (d == 2) { if (csr[s] > csr[s + 1]) { int t = csr[s]; csr[s] = csr[s + 1]; csr[s + 1] = t; } }
        else if (d > 2) {
            if (d <= 16) {
                for (int a = s + 1; a < e; a++) {
                    int x = csr[a], b = a - 1;
                    while (b >= s && csr[b] > x) { csr[b + 1] = csr[b]; --b; }
                    csr[b + 1] = x;
                }
            } else std::sort(csr + s, csr + e);
        }
    }

    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;
        for (int k = start[u], e = start[u + 1]; k < e; k++) {
            int v = csr[k];
            if (oncycle[v] && --deg2[v] == 1) queue[qt++] = v;
        }
    }

    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], idx = si[top - 1], now = sn[top - 1];
        int e = start[x + 1];
        while (idx < e && vis[csr[idx]]) ++idx;
        if (idx >= e) { --top; continue; }
        int tt = csr[idx];
        if (oncycle[x]) {
            int j = idx + 1;
            while (j < e && vis[csr[j]]) ++j;
            int has_next = (j < e);
            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 = has_next ? csr[j] : now;
            sx[top] = tt; si[top] = start[tt]; sn[top] = child_now; ++top;
        } else {
            vis[tt] = 1;
            put_int(tt, ' ');
            si[top - 1] = idx + 1;
            sx[top] = tt; si[top] = start[tt]; sn[top] = now; ++top;
        }
    }
    outp[-1] = '\n';
    di->stdout_size = (u64)(outp - di->stdout_ptr);
#ifdef LOCAL
    fwrite(lob, 1, di->stdout_size, stdout);
#endif
    return 0;
}

评测结果