Cod sursa(job #240022)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 6 ianuarie 2009 18:33:10
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#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");
	}
}