代码

// This code is AI-generated. (AI 生成的代码)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define IO(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
#define I(x) freopen(x".in","r",stdin)
#define R(x) freopen(x".ini","r",stdin),freopen(x".in","w",stdout)
using namespace std;
const int N=500010,inf=20020221;
static char ibuf[1 << 25], obuf[1 << 25];
static char *ip = ibuf, *op = obuf;
inline int read() {
	while((unsigned)(*ip - '0') > 9u) ip++;
	register int r = 0;
	while((unsigned)(*ip - '0') <= 9u) r = r * 10 + (*ip++ - '0');
	return r;
}
inline void wt(int x) {
	char t[12]; int k = 0;
	if (!x) t[k++] = '0';
	while (x) { t[k++] = (char)('0' + x % 10); x /= 10; }
	while (k) *op++ = t[--k];
}
inline void wtln(int x) { wt(x); *op++ = '\n'; }
inline void wtsp(int x) { wt(x); *op++ = ' '; }
struct edge {
	int to,nt,id;
	inline void init(int t,int n,int i) {
		to=t,nt=n,id=i;
	}
} e[N<<1];
int h[N],c=1,x,y;
inline void adde(int f,int t,int i) {
	e[++c].init(t,h[f],i),h[f]=c;
	e[++c].init(f,h[t],i),h[t]=c;
}
int n,m;
int ans[N],tot;

int ste[N],stp[N],top;
int cre[N],crp[N],cc,vis[N];
int oce[N],ocp[N],del;
inline bool fndc(int pos,int pi=0) {
	vis[pos]=1;
	for(int i=h[pos],tps; i; i=e[i].nt) {
		tps=e[i].to;
		if(i==pi)continue;
		ste[++top]=i;
		stp[top]=pos;
		if(vis[tps]) {
			while(1) {
				ocp[stp[top]]=oce[e[ste[top]].id]=1;
				if(stp[top--]==tps)break;
			}
			return 1;
		} else if(fndc(tps,i^1))return 1;
		if(ste[top]==i)--top;
	}
	return 0;
}
int tmp[N],cnt;
inline void dfs(int pos,int nex=inf) {
	vis[pos]=1,ans[++tot]=pos;
	int l=cnt,r;
	for(int i=h[pos]; i; i=e[i].nt)if(!vis[e[i].to])tmp[cnt++]=e[i].to;
	r=cnt,sort(tmp+l,tmp+r);
	for(int i=l,j=l+1; i<r; i=j,++j) {
		if(vis[tmp[i]])continue;
		while(j<r&&vis[tmp[j]])++j;
		if(j<r)dfs(tmp[i],tmp[j]);
		else if(del==0&&ocp[pos]&&ocp[tmp[i]]&&tmp[i]>nex)del=1;
		else dfs(tmp[i],nex);
	}
}
int main() {
	fread(ibuf, 1, sizeof(ibuf) - 1, stdin);
	n=read(),m=read();
	for(int i=1; i<=m; ++i)
		adde(read(),read(),i);
	fndc(1);
	memset(vis,0,sizeof vis);
	dfs(1);
	for(int i=1; i<n; ++i)
		wtsp(ans[i]);
	wtln(ans[n]);
	fwrite(obuf, 1, op - obuf, stdout);
}

评测结果