Pagini recente » Cod sursa (job #211478) | Cod sursa (job #1334391) | Cod sursa (job #1510624) | Cod sursa (job #2332201) | Cod sursa (job #240022)
Cod sursa(job #240022)
#include<stdio.h>
#define M 200001
#define N 100001
struct nod{ int inf;nod *urm;};
nod *p[N],*C[M];
int n,m,i,aa,bb,V[N],D[N],B[N],T[N],nsol,cnt,S[M],top;
void readd(),solve(),add_edge(),df(int nc),afisare(),update(int xx,int yy);
int main()
{
readd();
solve();
afisare();
return 0;
}
void readd()
{
freopen("biconex.in","rt",stdin);
freopen("biconex.out","wt",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++){scanf("%d%d",&aa,&bb);add_edge();}
}
void add_edge()
{
nod *paux;
paux=new nod;
paux->inf=aa;
paux->urm=p[bb];
p[bb]=paux;
paux=new nod;
paux->inf=bb;
paux->urm=p[aa];
p[aa]=paux;
}
void solve()
{
for(i=1;i<=n;i++)
if(!V[i])
{cnt=1;df(i);}
}
void df(int nc)
{ nod *paux;
V[nc]=1;D[nc]=B[nc]=cnt++;
for(paux=p[nc];paux;paux=paux->urm)
{ if(!V[paux->inf])
{ S[++top]=nc;S[++top]=paux->inf;
T[paux->inf]=nc;
df(paux->inf);
if(B[paux->inf]>=D[nc])
update(nc,paux->inf);
B[nc]=(B[nc]<B[paux->inf])?B[nc]:B[paux->inf];
continue;
}
if(paux->inf-T[nc])
B[nc]=(B[nc]<D[paux->inf])?B[nc]:D[paux->inf];
}
}
void update(int xx,int yy)
{ nod *qaux;
int xp,yp;
nsol++;
do
{ xp=S[top-1];yp=S[top];
qaux=new nod;qaux->inf=xp;qaux->urm=C[nsol];C[nsol]=qaux;
qaux=new nod;qaux->inf=yp;qaux->urm=C[nsol];C[nsol]=qaux;
top-=2;
}while((xp-xx)||(yp-yy));
}
void afisare()
{ nod *qaux;
printf("%d\n",nsol);
for(i=1;i<=nsol;i++)
{ for(qaux=C[i];qaux;qaux=qaux->urm)V[qaux->inf]=0;
for(qaux=C[i];qaux;qaux=qaux->urm)
{ if(V[qaux->inf])continue;
V[qaux->inf]=1;printf("%d ",qaux->inf);
}
printf("\n");
}
}