代码

#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;
inline int read() {
	register char c=getchar(),d=0;
	while(c>'9'||c<'0')d=c,c=getchar();
	register int r=0;
	while(c>='0'&&c<='9')r=(r<<1)+(r<<3)+c-'0',c=getchar();
	return d=='-'?-r:r;
}
inline void wt(int x) {
	if(x/10)wt(x/10);
	putchar(x%10+'0');
}
inline void wtln(int x) {
	if(x<0)x=-x,putchar('-');
	wt(x),putchar('\n');
}
inline void wtsp(int x) {
	if(x<0)x=-x,putchar('-');
	wt(x),putchar(' ');
}
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() {
	IO("travel");
	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]);
}

评测结果