Cod sursa(job #427243)

Utilizator adrianraduleaRadulea Adrian adrianradulea Data 27 martie 2010 17:51:00
Problema Componente biconexe Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include<stdio.h>
FILE *f,*g;
long t[3][400100],i,n,m,x,y,c[100100],fin[100100],nr,z,q,parinte[100100],viz[100100],viz2[100100],nivel[100100],low[100100],nrcomp,nrr,cc[100100],tt[3][200100];
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])
		 { 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(!viz2[t[1][p]]) { if(low[t[1][p]]<=nivel[k]) dfc(t[1][p]); else { nrcomp++; nrr++; cc[nrcomp]=nrr; tt[1][nrr]=k; tt[2][nrr]=nrr+1; nrr++; tt[1][nrr]=t[1][p]; dfc(t[1][p]);}}
     else if(parinte[k]!=t[1][p]&&nivel[t[1][p]]<nivel[k]) 
	  { x=k; nrcomp++; nrr++; cc[nrcomp]=nrr;
	    while(x!=t[1][p])
		 { tt[1][nrr]=x; nrr++; tt[2][nrr-1]=nrr;
		   x=parinte[x];
		 }
		tt[1][nrr]=x; 
	  }
	 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;
  
}