Cod sursa(job #427519)

Utilizator adrianraduleaRadulea Adrian adrianradulea Data 27 martie 2010 22:44:51
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 2.01 kb
#include<stdio.h>
FILE *f,*g;
long t[3][400100],i,n,m,x,y,c[100100],j,e,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]; 
           if(low[t[1][p]]>=nivel[k])
		     {  nrcomp++; cc[nrcomp]=nrr+1; ind++;
		        for(j=1; j<=e-2;j++) if(indice[st[j]]!=ind) { nrr++; tt[1][nrr]=st[j]; tt[2][nrr]=nrr+1; indice[st[j]]=ind; }  
				tt[2][nrr]=0;
		         e=2; st[1]=k; st[2]=t[1][p]; 
			 }
		   dfc(t[1][p]); 
		 }
	  }
	 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);
  if(e) { nrcomp++; cc[nrcomp]=nrr+1; ind++;
          for(j=1; j<=e-2;j++) if(indice[st[j]]!=ind) { nrr++; tt[1][nrr]=st[j]; tt[2][nrr]=nrr+1; indice[st[j]]=ind; }  
          tt[2][nrr]=0;
        }		  
  fprintf(g,"%ld\n",nrcomp-1);
  for(i=2;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;
  
}