Cod sursa(job #239889)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 6 ianuarie 2009 03:01:48
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.33 kb
#include<stdio.h>
#define M 200001
#define N 100001
struct nod{ int inf;nod *urm;};
nod *p[N],*cbc[M];
int n,m,i,a[M],b[M],viz[N],niv[N],low[N],dad[N],stack[M],top,ncb,dc,ee,
cb[M],j;
void readd(),solve(),prints(),add_edge(),df(int nc,int nivel),
hd(int ic,int nr),sw(int i1,int i2),last();
int main()
{
	readd();
	solve();
	last();
	prints();
	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",&a[i],&b[i]);add_edge();}
}
void add_edge()
{
	nod *paux;
	paux=new nod;
	paux->inf=i;
	paux->urm=p[b[i]];
	p[b[i]]=paux;
	paux=new nod;
	paux->inf=i;
	paux->urm=p[a[i]];
	p[a[i]]=paux;
}
void solve()
{
	df(1,0);
}
void df(int nc,int nivel)
{     nod *paux,*qaux;
      int ec,nv,dcc;
      viz[nc]=1;
      low[nc]=niv[nc]=nivel+1;
      for(paux=p[nc];paux;paux=paux->urm)
      { ec=paux->inf;
	nv=a[ec]+b[ec]-nc;
	if(nv==dad[nc])continue;
	if(!viz[nv])
	{ dad[nv]=nc;stack[++top]=ec;df(nv,nivel+1);}
	low[nc]=(low[nc]<low[nv])?low[nc]:low[nv];
	if(nc>1&&low[nc]==niv[nc])
	{ ncb++;dc=0;
	  for(;;)
	  { ee=stack[top];
	    cb[++dc]=a[ee];
	    cb[++dc]=b[ee];
	    top--;
	    if(ee==ec||!top)break;
	  }
	  for(j=dc/2;j;j--)hd(j,dc);
	  for(j=dc;j;j--){sw(1,j);hd(1,j-1);}
	  dcc=dc;dc=0;
	  for(j=1;j<=dcc;j++)
	  { if(cb[j]==cb[j-1])continue;
	    cb[++dc]=cb[j];
	  }
	  for(j=1;j<=dc;j++)
	  { qaux=new nod;qaux->inf=cb[j];qaux->urm=cbc[ncb];cbc[ncb]=qaux;}
	}
      }
}
void last()
{     int dcc;nod *qaux;
      if(top)
      { ncb++;dc=0;
	  for(;top;)
	  { ee=stack[top];
	    cb[++dc]=a[ee];
	    cb[++dc]=b[ee];
	    top--;
	  }
	  for(j=dc/2;j;j--)hd(j,dc);
	  for(j=dc;j;j--){sw(1,j);hd(1,j-1);}
	  dcc=dc;dc=0;
	  for(j=1;j<=dcc;j++)
	  { if(cb[j]==cb[j-1])continue;
	    cb[++dc]=cb[j];
	  }
	  for(j=1;j<=dc;j++)
	  { qaux=new nod;qaux->inf=cb[j];qaux->urm=cbc[ncb];cbc[ncb]=qaux;}
      }
}
void sw(int i1,int i2)
{ int aux=cb[i1];cb[i1]=cb[i2];cb[i2]=aux;}
void hd(int ic,int nr)
{
	int is=ic<<1;
	if(is>nr)return;
	if(is<nr)if(cb[is]<cb[is+1])is++;
	if(cb[ic]<cb[is]){sw(is,ic);hd(is,nr);}
}
void prints()
{       nod *paux;
	printf("%d\n",ncb);
	for(i=1;i<=ncb;i++)
	 { for(paux=cbc[i];paux;paux=paux->urm)printf("%d ",paux->inf);
	   printf("\n");
	 }
}