今天调了一上午都不对,大佬救救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;
}