先放上我的暴T代码 球球屏幕前的大佬看看哪出问题了叭
#include <bits/stdc++.h>
using namespace std;
const int MAX=50000;
int n,m;
struct edgem{
int next,to;
}e[MAX<<1];
int head[MAX],tot;
int q[MAX],l,r;
inline void add(int ax,int ay)
{
e[++tot].to=ay;
e[tot].next=head[ax];
head[ax]=tot;
}
int lin[MAX],c[MAX],f[MAX],pre[MAX];
inline int find(int xu)
{
return xu==f[xu] ? xu : f[xu]=find(f[xu]);
}
int cnt,be[MAX];
inline int lca(int x,int y)
{
++cnt;
while(1)
{
x=find(x);
if(be[x]==cnt) return x;
else{
be[x]=cnt;
x=pre[lin[x]];
}
swap(x,y);
}
}
inline void sakura(int x,int y,int t)
{
while(find(x)!=t)
{
pre[x]=y;
y=lin[x];
/*+*/c[y]=1,q[++r]=y;
f[x]=t,f[y]=t;
x=pre[y];
}
}
inline bool bfs(int xu)
{
l=1,r=0;
for(int i=1;i<=n;++i) f[i]=i;
memset(c,0,sizeof(c));
memset(pre,0,sizeof(pre));
c[xu]=1;q[++r]=xu;
while(l<=r)
{
int now=q[l++];
for(int i=head[now];i;i=e[i].next)
{
int nxt=e[i].to;
if(c[nxt]==2 || find(nxt)==find(now)) continue;
else if(!c[nxt])
{
c[nxt]=1,pre[nxt]=now;
if(!lin[nxt])
{
do{
lin[nxt]=pre[nxt];
int ori=lin[now];
lin[now]=nxt;
nxt=ori;/*swap(lin[now],nxt);*/
now=pre[ori];
}while(now);
return true;
}
c[lin[nxt]]=1,q[++r]=lin[nxt];
}
else
{
int t=lca(now,nxt);
sakura(now,nxt,t);
sakura(nxt,now,t);
}
}
}
return false;
}
int main()
{
cin>>n>>m;
int ax,ay;
for(int i=1;i<=m;++i)
{
scanf("%d%d",&ax,&ay);
add(ax,ay);
add(ay,ax);
}
int ans=0;
for(int i=1;i<=n;++i)
{
if(lin[i]) continue;
if(bfs(i)) ++ans;
}
cout<<ans<<endl;
for(int i=1;i<=n;++i) printf("%d ",lin[i]);
return 0;
}