Cod sursa(job #427931)

Utilizator adrianraduleaRadulea Adrian adrianradulea Data 28 martie 2010 16:26:11
Problema Componente biconexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 2.08 kb
#include<stdio.h>
FILE *f,*g;
long t[3][400100],i,n,m,x,y,c[100100],j,e,ok,st[100000],fin[100100],nr,z,q,parinte[100100],viz[100100],viz2[100100],nivel[100100],low[100100],nrcomp,nrr,cc[100100],tt[3][200100],maxim[100100],indice[100100],ind;
void df(long k,long niv)
{ viz[k]=1; long p=c[k]; nivel[k]=niv; low[k]=niv;
  while(p)
   { if(!viz[t[1][p]]) { parinte[t[1][p]]=k; df(t[1][p],niv+1); }
     else if(nivel[t[1][p]]<nivel[k]&&parinte[k]!=t[1][p]) 
	  { x=k; 
	    while(x!=t[1][p])
		 { if(low[x]>nivel[t[1][p]]) low[x]=nivel[t[1][p]];  
		   x=parinte[x];
		 }
	  }
	 p=t[2][p];  
   }	
}    
void dfc(long k)
{ viz2[k]=1; long p=c[k];
  while(p)
   { if(t[1][p]!=parinte[k]) {
	 if(viz2[t[1][p]]&&nivel[t[1][p]]<nivel[k])
       { e++; st[e]=k; e++; st[e]=t[1][p]; }
	  else if(!viz2[t[1][p]]) 
	   { parinte[t[1][p]]=k; e++; st[e]=k; e++; st[e]=t[1][p]; dfc(t[1][p]); 
	     if(low[t[1][p]]>=nivel[k])
		   {  nrcomp++; cc[nrcomp]=nrr+1; ind++;
		      while(st[e]!=t[1][p]||st[e-1]!=k) 
			  { if(indice[st[e]]!=ind) { nrr++; tt[1][nrr]=st[e]; tt[2][nrr]=nrr+1; indice[st[e]]=ind; }
			    if(indice[st[e-1]]!=ind) { nrr++; tt[1][nrr]=st[e-1]; tt[2][nrr]=nrr+1; indice[st[e-1]]=ind; }
				e-=2;
			  }
			   if(e>=2){
			   if(indice[st[e]]!=ind) { nrr++; tt[1][nrr]=st[e]; tt[2][nrr]=nrr+1; indice[st[e]]=ind; }
			   if(indice[st[e-1]]!=ind) { nrr++; tt[1][nrr]=st[e-1]; tt[2][nrr]=0; indice[st[e-1]]=ind; }
			   e-=2;}
		   }
	   }}
	  p=t[2][p];
   }
}
int main()
{ f=fopen("biconex.in","r"); g=fopen("biconex.out","w");
  fscanf(f,"%ld%ld",&n,&m);
  for(i=1;i<=m;i++)
   { fscanf(f,"%ld%ld",&x,&y);
     if(c[x]==0) { nr++; c[x]=nr; t[1][nr]=y; fin[x]=nr; }
	 else { nr++; t[2][fin[x]]=nr; t[1][nr]=y; fin[x]=nr; }
	 z=x; x=y; y=z;
	 if(c[x]==0) { nr++; c[x]=nr; t[1][nr]=y; fin[x]=nr; }
	 else { nr++; t[2][fin[x]]=nr; t[1][nr]=y; fin[x]=nr; }
   }
  df(1,1);
  dfc(1);	
  fprintf(g,"%ld\n",nrcomp);
  for(i=1;i<=nrcomp;i++)
   { q=cc[i];
     while(q) { fprintf(g,"%ld ",tt[1][q]); q=tt[2][q]; }
	 fprintf(g,"\n");
   }
  fclose(g);
  return 0;
  
}