80分---蒟蒻求助!
查看原帖
80分---蒟蒻求助!
346689
death1楼主2020/10/31 11:24

今天调了一上午都不对,大佬救救jvruo吧!

#include<bits/stdc++.h>
using namespace std;
const int M=1e4+16;
int n,m,nxt[M],head[M],to[M],t=0,b[M>>1],bl[M>>1],h[5007][507],c[M>>1],tail=0;
int ans;
void add(int x,int y)
{
	nxt[++t]=head[x];
	head[x]=t;
	to[t]=y;
}
void hfs(int x,int fa)//分支入队 
{
	c[++tail]=x,b[x]=tail;
	int u=0;
	for(int i=head[x];i;i=nxt[i])
	{
		int p=to[i];
		if(p==fa||bl[p]) continue;
		if(b[p]) 
		{
        continue;
		}
		else h[x][++u]=p; 
	}
	sort(h[x]+1,h[x]+1+u);
	for(int i=1;i<=u;++i)
	if(!b[h[x][i]]) 
	{
	b[h[x][i]]=1;
	hfs(h[x][i],x);
	}
}
void bfs(int x,int fa,int iu,int ip)
{
	for(int i=head[x];i;i=nxt[i])
	{
		int p=to[i];
		if(p==fa||b[p]>b[x]||p==ip) continue;
		if(!b[p]&&x!=iu) hfs(p,x);//有分支要将分支入队 
		else{
			if(p<iu&&iu<x) ans=min(ans,b[x]);
			bfs(p,x,iu,ip);//继续找 
		}
	}
}
void dfs(int x,int sum,int fa)
{
	c[++tail]=x,b[x]=tail;//入队,记标号 
	if(sum==n) return;
	int u=0;
	for(int i=head[x];i;i=nxt[i])
	{
		int p=to[i];
		if(p==fa||bl[p]) continue;
		if(b[p]) //判环 
		{
		tail--;
		ans=99999;
		bfs(x,p,x,p);//找到环中序号最小的i(c[i]>x&&c[i-1]<x) 
		if(ans!=99999)//找到了 
		{
		//for(int j=1;j<=ans-1;j++) bl[c[j]]=1;
		for(int j=ans;j<=tail;j++) b[c[j]]=0;
		tail=ans-1;
		}
		for(int j=1;j<=tail;j++) bl[c[j]]=1;//固定序列 
		dfs(x,tail,p);//继续找 
		return;
		}
		else h[x][++u]=p; 
	}
	sort(h[x]+1,h[x]+1+u);//为与x相连的城市排序 
	for(int i=1;i<=u;++i)
	if(!b[h[x][i]]) 
	{
	b[h[x][i]]=1;
	dfs(h[x][i],sum+1,x);
	}
}
int main()
{
    /*freopen("travel.in","r",stdin);
	freopen("travel.out","w",stdout);*/
	memset(head,0,sizeof(head));
	memset(b,0,sizeof(b));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i) 
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	b[1]=1;
	dfs(1,0,0);
	for(int i=1;i<=n;++i) printf("%d ",c[i]);
	return 0; 
} 
2020/10/31 11:24
加载中...