代码

#include<cstdio>
#include<cstring>
#define IO(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
const int str=1<<15;
const char* endl="\n";
struct Reader {
	char buf[str],*s,*t;
	Reader():s(buf),t(buf) {};
	inline char gt() {
		return s==t&&((t=(s=buf)+fread(buf,1,str,stdin))==s)?EOF:(*s++);
	}
	template<typename T>Reader&operator>>(T&x) {
		register char c=0,d;
		while(c<'0'||c>'9')d=c,c=gt();
		x=0;
		while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=gt();
		if(d=='-')x=-x;
		return *this;
	}
} cin;
struct Writer {
	char buf[str],*s,*t;
	Writer():s(buf),t(buf+str) {}
	~Writer() {
		fwrite(buf,1,s-buf,stdout);
	}
	inline void pt(char c) {
		(s==t)?(fwrite(s=buf,1,str,stdout),*s++=c):(*s++=c);
	}
	template<typename T>Writer&operator<<(T x) {
		if(!x)return pt('0'),*this;
		if(x<0)pt('-'),x=-x;
		register char a[30],t=0;
		while(x)a[t++]=x%10,x/=10;
		while(t--)pt(a[t]+'0');
		return *this;
	}
	Writer&operator<<(const char*s) {
		while(*s)pt(*s++);
		return *this;
	}
} cout;
const int N=500010,inf=20020221;
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;
	register int i,tps;
	for(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;
	register int l=cnt,r,i,j;
	for(i=h[pos]; i; i=e[i].nt)if(!vis[e[i].to])tmp[cnt++]=e[i].to;
	r=cnt;
	for(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() {
	cin>>n>>m;
	register int i,pos,x,y;
	for(i=1; i<=m; ++i)cin>>x>>y,addt(x,y,i);
	for(pos=n; pos>=1; --pos)
		for(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(i=1; i<n; ++i)cout<<ans[i]<<" ";
	cout<<ans[n]<<endl;
}

评测结果