代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define IO(x) freopen(x".in","r",stdin),freopen(x".out","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],te[N<<1];
int h[N],c=1,x,y,tc=1,th[N];
inline void addt(int f,int t,int i) {
	te[++tc].init(t,th[f],i),th[f]=tc;
	te[++tc].init(f,th[t],i),th[t]=tc;
}
inline void adde(int f,int t,int i) {
	e[++c].init(t,h[f],i),h[f]=c;
}
int n,m;
int ans[N],tot;
int stp[N],top;
int vis[N];
int 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(e[i].id==pi)continue;
		stp[++top]=pos;
		if(vis[tps]) {
			while(1) {
				ocp[stp[top]]=1;
				if(stp[top--]==tps)break;
			}
			return 1;
		} else if(fndc(tps,e[i].id))return 1;
		if(stp[top]==pos)--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;
	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() {
	n=read(),m=read();
	for(int i=1; i<=m; ++i)addt(read(),read(),i);
	for(int pos=n; pos>=1; --pos)
		for(int i=th[pos]; i; i=te[i].nt)
			adde(te[i].to,pos,te[i].id);
	fndc(1);
	memset(vis,0,sizeof vis);
	dfs(1);
	for(int i=1; i<n; ++i)wtsp(ans[i]);
	wtln(ans[n]);
}

评测结果