代码

#include <stdio.h>
#include <algorithm>

namespace IO {
	const int BUF_SIZE = 1 << 24;
	char in_buf[BUF_SIZE], out_buf[BUF_SIZE];
	char *p_in_buf = in_buf + BUF_SIZE;
	char *p_out_buf = out_buf;
	
	
	inline char get_char() {
		if (p_in_buf == in_buf + BUF_SIZE) {
			fread(in_buf, 1, BUF_SIZE, stdin), p_in_buf = in_buf;
		}
		return *(p_in_buf++);
	}
	
	inline void put_char(char x) {
		if (p_out_buf == out_buf + BUF_SIZE) {
			fwrite(out_buf, 1, BUF_SIZE, stdout), p_out_buf = out_buf;
		}
		*(p_out_buf++) = x;
	}
	
	inline void flush() {
		if (p_out_buf != out_buf) {
			fwrite(out_buf, 1, p_out_buf - out_buf, stdout);
			p_out_buf = out_buf;
		}
	}
}

#define getchar() IO::get_char()
#define putchar(x) IO::put_char(x)

inline int getint() {
	int x = 0;
	char c = getchar();
	while (c <= 32) c = getchar();
	int f = 1;
	if (c == '-') f = -1, c = getchar();
	while (c > 32) x = x * 10 + c - 48, c = getchar();
	return x * f;
}

template <class T>
inline void _putint(T x) {
	return x ? _putint(x / 10), putchar(48 + x % 10), void() : void();
}

template <class T>
inline void putint(T x) {
	if (x < 0) return putchar('-'), putint(-x), void();
	return x == 0 ? putchar('0'), void() : _putint(x), void();
}

const int MAXN = 500005;

int n, m;

struct edge {
	int u, v, id;
};

bool operator < (const edge &a, const edge &b) {
	return a.u < b.u || (a.u == b.u && a.v < b.v);
}

edge edges[MAXN * 2];
edge *first[MAXN];

int stack[MAXN];
int stack_eid[MAXN];
bool instack[MAXN];
int top;
bool found;

bool is_on_cycle[MAXN];

void dfs(int u, int last) {
	stack[++top] = u;
	instack[u] = true;
	for (edge *e = first[u]; e->u == u; e++) {
		int v = e->v;
		if (v == last) continue;
		if (instack[v]) {
			found = true;
			is_on_cycle[e->id] = true;
			while (stack[top] != v) {
				is_on_cycle[stack_eid[top - 1]] = true;
				--top;
			}
			return;
		}
		stack_eid[top] = e->id;
		dfs(v, u);
		if (found) return;
	}
	instack[u] = false;
	--top;
}

int ans_idx;

bool visit[MAXN];
bool del;

void dfs(int u) {
	putint(u), putchar(" \n"[++ans_idx == n]);
	visit[u] = true;
	++top;
	bool done = false;
	for (edge *e = first[u]; e->u == u; e++) {
		int v = e->v;
		if (visit[v]) continue;
		edge *e1 = e + 1;
		while (e1->u == u && visit[e1->v]) ++e1;
		if (e1->u == u) {
			stack[top] = e1->v;
		} else {
			--top;
			done = true;
		}
		if (!del && is_on_cycle[e->id] && v > stack[top]) {
			del = true;
		} else {
			dfs(v);
		}
	}
	if (!done) --top;
}

int main() {
	n = getint(), m = getint();
	if (n == 1) {
		return putchar('1'), putchar('\n'), IO::flush(), 0;
	}
	for (int i = 0; i < m; i++) {
		int u, v;
		u = getint(), v = getint();
		edges[i * 2] = (edge){u, v, i};
		edges[i * 2 + 1] = (edge){v, u, i};
	}
	std::sort(edges, edges + 2 * m);
	first[1] = edges;
	for (int i = 1; i < 2 * m; i++) {
		if (edges[i].u != edges[i - 1].u) {
			first[edges[i].u] = edges + i;
		}
	}
	dfs(1, 0);
	top = 0;
	stack[0] = n + 1;
	dfs(1);
	IO::flush();
}

评测结果