代码

#include<bits/stdc++.h>

#define For(i, l, r) for(int i = (l), i##end = (int)(r); i <= i##end; ++ i)
#define Fordown(i, r, l) for(int i = (r), i##end = (int)(l); i >= i##end; -- i)
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl

using namespace std;

template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, T b) { return b > a ? a = b, 1 : 0; }

inline int read() {
    int x(0), sgn(1); char ch(getchar());
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;
    for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);
    return x * sgn;
}

void File() {
#ifdef zjp_shadow
    freopen ("P5049.in", "r", stdin);
    freopen ("P5049.out", "w", stdout);
#endif
}

const int N = 5e5 + 1e3, M = N << 1, inf = 0x7f7f7f7f;

int n, m;

set<int> S[N];
int Head[N], Next[M], to[M], e = 0;

inline void add_edge(int u, int v) {
    to[++ e] = v; Next[e] = Head[u]; Head[u] = e;
	S[u].insert(v); S[v].insert(u);
}

bool vis[N], inc[N];
int ans[N], pre[N], len, pos;

inline void Paint(int u, int v) {
    pos = u;
    inc[u] = true;
    while (v != u) {
        inc[v] = true, v = pre[v];
    }
}

int dep[N];

void Dfs_Init(int u = 1, int fa = 0) {
    if (vis[u]) return ;
    dep[u] = dep[fa] + 1;
    vis[u] = true;
    for (int i = Head[u], v = to[i]; i; v = to[i = Next[i]]) 
        if (v != fa) {
            if (vis[v] && dep[u] < dep[v]) Paint(u, v);
            else pre[v] = u, Dfs_Init(v, u);
        }
}

inline int Get(int u) {
	while (!S[u].empty()) {
		auto v = S[u].begin();
		if (vis[*v]) S[u].erase(v);
		else return *v;
	}
    return inf;
}

int stk[N], sta[N], top;

void Dfs(int u) {
    if (!vis[u]) ans[++ len] = u;
    vis[u] = true;
    while(Get(u) < inf) Dfs(Get(u));
}

int minv[N], best = inf;

inline int Check() {
	Fordown(i, top - 1, 1)
		if (inc[stk[i]] && minv[stk[i]] != inf) return minv[stk[i]];
	return inf;
	//   return best;
}

bool back = true;

int main() {

	File();

	n = read(); m = read();
	For (i, 1, m) {
		int u = read(), v = read();
		add_edge(u, v);
		add_edge(v, u);
	}

	Dfs_Init(); 
	Set(vis, false); 

	stk[top = 1] = 1;
	while (top) {
		int u = stk[top];
		if (!vis[u]) ans[++ len] = u;
		vis[u] = true;
		minv[stk[top - 1]] = Get(stk[top - 1]);
		if (Get(u) == inf) { -- top; continue ; }
		if (!inc[u])
			Get(stk[++ top] = Get(u));
		else {
			bool flag = true;
			for (int i = Head[u], v = to[i]; i; v = to[i = Next[i]]) 
				if (!vis[v] && !inc[v]) flag = false;
			if (flag && back && Check() < Get(u)) {
				back = false;
				-- top;
				while (inc[stk[top]]) Dfs(stk[top --]);
			} else {
				stk[++ top] = Get(u);
			}
		}
	}

	For (i, 1, len)
		printf ("%d%c", ans[i], i == iend ? '\n' : ' ');

	return 0;

}

评测结果