Cod sursa(job #264268)

Utilizator drag0shSandulescu Dragos drag0sh Data 21 februarie 2009 20:44:02
Problema Componente biconexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 2.04 kb
#include <stdio.h>
#include <string.h>
#define NMAX 100001

FILE *f=fopen("biconex.in","r"),*g=fopen("biconex.out","w");
int num,n,vfs,nrfii,nr,start=1;
int dfn[NMAX],low[NMAX],art[NMAX],vazut[NMAX];

struct nod{
  int info;
  nod* adr_urm;
}*a[NMAX],*sol[2*NMAX];

struct muchie{int f,t;}s[NMAX];

void adauga(nod* &v,int nr){
  nod* c=new nod;
  c->info=nr;
  c->adr_urm =v;
  v=c;
}

void citire(){
  int m,x,y;
  fscanf(f,"%d%d",&n,&m);
  while(m) {
    m--;
    fscanf(f,"%d%d",&x,&y);
    adauga(a[x],y);
    adauga(a[y],x);
  }
}

void initializare(){
  int i;
  for(i=n;i>0;i--)dfn[i]=low[i]=-1;
  s[0].f=start;
  s[0].t=-1;
  vfs=0;
}

int min(int x,int y){
  return x<y?x:y;
}

void biconex(int,int);
void preafisare(int,int);
void afisare();

int main(){
  int i;
  citire();
  initializare();
  biconex(start,-1);
  /*
  if(nrfii>1)art[start]=1;
  fprintf(g,"punctele de articulatie sunt:");
  for(i=1;i<=n;i++)
    if(art[i]) fprintf(g,"%d",i);
  fprintf(g,"\n");
     */   
  afisare();

  return 0;
}

void biconex(int u,int tu){
  int x,p;
  nod *c=a[u];
  dfn[u]=low[u]=++num;
  while(c){
    x=c->info;
    if(x!=tu&&dfn[x]<dfn[u]){
      s[++vfs].f=x;
      s[vfs].t=u;
    }
    if(dfn[x]==-1){
     // if(u==start)nrfii++;
      biconex(x,u);
      low[u]=min(low[x],low[u]);
      if(low[x]>=dfn[u]){
	//if(u!=start)art[u]=1;
	preafisare(x,u);}
      }
    else
      if(x!=tu) low[u]=min(low[u],dfn[x]);
    c=c->adr_urm;
  }
}
 
void preafisare(int x,int u){
  muchie p;
  int cc;
  cc=0;
  nr++;
  //  fprintf(g,"componenta biconexa %d contine muchiile\n",nr);
  memset(vazut,0,sizeof(vazut));
  do{
    p=s[vfs--];
    //   fprintf(g,"%d %d\n",p.t,p.f);
    // if(!vazut[p.t])adauga(sol[nr],p.t);
    // if(!vazut[p.f])adauga(sol[nr],p.f);
    // vazut[p.t]=1;
    // vazut[p.f]=1;
    adauga(sol[nr],p.t);
    cc++;
    }
  while(p.t!=u||p.f!=x);
   if(cc==1)adauga(sol[nr],p.f);
}

void afisare(){
 fprintf(g,"%d\n",nr);
 
  while(nr){
    nod *c=sol[nr];
    while(c){
      fprintf(g,"%d ",c->info);
      c=c->adr_urm;
    }
    fprintf(g,"\n");
    nr--;
  }
}