RT 感谢

Record

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rd read()
#define Elaina 0
inline int read(){
	int f=1,x=0;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) f=(ch=='-'?-1:1);
	for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
	return f*x;
}
const int N=500010;
const int inf=0x7fffffff;

int n,m,vis[N],ans[N],cnt,f[N],ring[N],flag,tmp,temp,head[N],idx;
struct EDGE{
	int nxt,to;
}e[N<<1];

void add(int x,int y){
	e[++idx].to=y;
	e[idx].nxt=head[x];
	head[x]=idx;
}

struct Node{
	int frm,to;
}node[N<<1];

bool cmp(Node x,Node y){
	return x.to>y.to;
}

void dfs1(int x,int fa){
	if(vis[x]) return ;
	vis[x]=1;
	ans[++cnt]=x;
	for(int i=head[x];i;i=e[i].nxt){
		int to=e[i].to;
		if(to==fa) continue;
		dfs1(to,x);
	}
}

void GetRing(int x,int fa){
	if(flag) return;
	if(!f[x]) f[x]=fa;
	else if(f[x]!=fa){
		while(x!=fa){
			ring[fa]=1;
			fa=f[fa];
		}
		ring[x]=1;
		flag=1;
		return;
	}
	for(int i=head[x];i;i=e[i].nxt){
		int to=e[i].to;
		if(to==fa) continue;
		GetRing(to,x);
	}
}

void dfs2(int x,int fa){
	if(vis[x]) return;
	vis[x]=1;
	ans[++cnt]=x;
	if(ring[x]){
		int flag=0;
		for(int i=head[x];i;i=e[i].nxt){
			if(temp) break;
			int to=e[i].to;
			if(ring[to]){
				i=e[i].nxt;
				while(e[i].to) i=e[i].nxt;
				if(i) tmp=e[i].to;
				else if(to>tmp){
					flag=1,temp=1;
				}
				break;
			}
		}
		for(int i=head[x];i;i=e[i].nxt){
			int to=e[i].to;
			if(ring[to] && flag) continue;
			dfs2(to,x);
		}
	}else{
		for(int i=head[x];i;i=e[i].nxt){
			int to=e[i].to;
			if(to==x) continue;
			dfs2(to,x);
		}
	}
}

signed main(){
	n=rd,m=rd;
	int u,v;
	for(int i=1;i<=m;i++){
		u=rd,v=rd;
		node[i]={u,v};
		node[i+m]={v,u};
	}
	sort(node+1,node+1+2*m,cmp);
	for(int i=1;i<=2*m;i++){
		add(node[i].frm,node[i].to);
	}
	if(m==n-1){
		dfs1(1,0);
	}else{
		GetRing(1,1);
		flag=0;
		tmp=inf;
		dfs2(1,0);
	}
	for(int i=1;i<=cnt;i++){
		printf("%lld ",ans[i]);
	}
	return Elaina;
}

关注東雪蓮谢谢喵~