#include<bits/stdc++.h>
using namespace std;
int m,n,a1[500001],a2[500001],a3,ans1,d[500001][500001],d1[500001],ans[500001],e[1000001],e1[1000001],e2[500001],u,v,e5,e6,ans2[500001];
bool b[500001],ok,ok1;
void abc(int c)
{
++ans1;
if(ans1>n)return;
ans[ans1]=c;
for(int i=1;i<=m;++i)
{
if(a1[i]==c&&(b[a2[i]])==0)
{
d[c][++d1[c]]=a2[i];
}
else if(a2[i]==c&&(b[a1[i]])==0)
{
d[c][++d1[c]]=a1[i];
}
}
b[c]=1;
sort(d[c],d[c]+d1[c]+1);
for(int i=1;i<=d1[c];++i)
{
abc(d[c][i]);
}
}
void abc1(int c)
{
if(b[c])return;
b[c]=1;
int e3=e2[c];
d1[c]=0;
while(e3)
{
if(e3==e5||b[e[e3]]||e3==e6)
{
e3=e1[e3];
continue;
}
d[c][++d1[c]]=e[e3];
e3=e1[e3];
}
sort(d[c]+1,d[c]+d1[c]+1);
for(int i=1;i<=d1[c];i++)
{
if(ok==0)
{
if(d[c][i]>ans[++ans1])
{
ok1=1;
return;
}
if(d[c][i]<ans[ans1])
{
ok=1;
ans[ans1]=d[c][i];
}
}
else ans[++ans1]=d[c][i];
abc1(d[c][i]);
if(ok1)return;
}
}
int main()
{
//freopen("travel.in","r",stdin);
//freopen("travel.out","w",stdout);
scanf("%d%d",&n,&m);
if(m==n-1)
{
for(int i=1;i<=m;++i)
{
scanf("%d%d",&a1[i],&a2[i]);
}
abc(1);
for(int i=1;i<=n;i++)printf("%d ",ans[i]);
return 0;
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
e[(i<<1)-1]=v;
e1[(i<<1)-1]=e2[u];
e2[u]=(i<<1)-1;
e[i<<1]=u;
e1[i<<1]=e2[v];
e2[v]=i<<1;
}
memset(ans,0x3f,sizeof(ans));
memset(ans2,0x3f,sizeof(ans2));
ans[1]=1;
ans2[1]=1;
for(int j=1;j<=m;j++)
{
e5=j<<1;
e6=e5-1;
ans1=1;
ok=0;
ok1=0;
memset(b,0,sizeof(b));
abc1(1);
if(ok&&ans1==n)for(int i=1;i<=n;i++)ans2[i]=ans[i];
else for(int i=1;i<=n;i++)ans[i]=ans2[i];
}
for(int i=1;i<=n;i++)printf("%d ",ans2[i]);
return 0;
}
Compilation | N/A | N/A | Compile Error | Score: N/A | 显示更多 |