P5049 旅行（数据加强版）(基环树)

做法

把环找出来，如果在环上(u,v)两点的时候，u的其他子树都走完了，v上第一个还有除v存在的子树没走完的祖先，祖先的最小子节点小于v，则回去

Code

#include<bits/stdc++.h>

typedef int LL;

const LL maxn=1e6+9,inf=0x3f3f3f3f;

inline LL Read(){

	LL x(0),f(1); char c=getchar();

	while(c<'0' || c>'9'){

		if(c=='-') f=-1; c=getchar();

	}

	while(c>='0' && c<='9'){

		x=(x<<3)+(x<<1)+c-'0'; c=getchar();

	}return x*f;

}

struct node{

	LL to,nxt;

}dis[maxn<<1];

LL n,m,num,top,op;

LL head[maxn],visit[maxn],vis[maxn],sta[maxn],ans[maxn],size[maxn];

std::vector<LL> G[maxn];

inline void Add(LL u,LL v){

	dis[++num]=(node){v,head[u]}; head[u]=num;

}

LL Dfs1(LL u,LL fa){

	visit[u]=true; sta[++top]=u;

	for(LL i=0;i<G[u].size();++i){

		LL v(G[u][i]); if(v==fa) continue;

		if(visit[v]){

			LL nw; //printf("%d\n",u);

			do{

				nw=sta[top--]; vis[nw]=1;

			}while(nw!=v);

			return true;

		}

		if(Dfs1(v,u)) return true;

	}

	--top;

	return false;

}

void Dfs2(LL u,LL mi){

	visit[u]=1; ans[++top]=u; LL tmp(inf);

	if(vis[u] && !op){

		LL i(0);

		for(;i<G[u].size();++i){

			if(visit[G[u][i]]) continue;

			if(vis[G[u][i]]) break;

		}

		for(++i;i<G[u].size();++i){

			if(visit[G[u][i]]) continue;

			tmp=std::min(tmp,G[u][i]);

		}

	}

	if(tmp==inf) tmp=mi;

	for(LL i=0;i<G[u].size();++i){

		LL v(G[u][i]); if(visit[v]) continue;

		if(!op && vis[u] && vis[v] && v>tmp){

			op=1; continue;

		}

		Dfs2(v,tmp);

	}

}

int main(){

	n=Read(); m=Read();

	for(LL i=1;i<=m;++i){

		LL u(Read()),v(Read());

		G[u].push_back(v); G[v].push_back(u);

	}

	for(LL i=1;i<=n;++i) std::sort(G[i].begin(),G[i].end());

	Dfs1(1,0);

	memset(visit,0,sizeof(visit)); top=0;

	Dfs2(1,inf);

	for(LL i=1;i<=n;++i) printf("%d ",ans[i]);

	return 0;

}

巴特西

P5049 旅行（数据加强版）(基环树)

做法

Code

最新文章

热门文章