Cod sursa(job #314981)

Utilizator mlazariLazari Mihai mlazari Data 13 mai 2009 21:53:49
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.79 kb
#include<stdio.h>
#define NMAX 100003
#define INF 333333
#define ROOT 1

struct lista {
  int x;
  lista *next;
};

struct muchie {
  int x,y;
};

lista *v[NMAX],*comp[NMAX];
muchie s[NMAX];
int ind[NMAX],t[NMAX],mr[NMAX],id=0,i,ns=0,nc=0,n,m,rc=0;

void adauga(lista* &l,int y) {
  lista *q=new lista;
  q->x=y;
  q->next=l;
  l=q;
}

void adaugaMuchie(int x,int y) {
  s[++ns].x=x;
  s[ns].y=y;
}

void scoateMuchie(int &x,int &y) {
  x=s[ns].x;
  y=s[ns--].y;
}

void memoreazaComponenta(int x,int y) {
  int xx,yy;
  comp[nc]=NULL;
  do {
    scoateMuchie(xx,yy);
    adauga(comp[nc],yy);
  } while(((xx!=x)||(yy!=y)));
  adauga(comp[nc++],x);
}

void citeste() {
  int i,x,y;
  freopen("biconex.in","r",stdin);
  scanf("%d %d",&n,&m);
  for(i=1;i<=n;i++) {
    v[i]=NULL;
    ind[i]=0;
    t[i]=-1;
    mr[i]=INF;
  }
  for(i=0;i<m;i++) {
    scanf("%d %d",&x,&y);
    adauga(v[x],y);
    adauga(v[y],x);
  }
  fclose(stdin);
}

void biconex(int nod) {
  ind[nod]=++id;
  lista *q=v[nod];
  int im=INF,ic=INF;
  while(q) {
    if(t[nod]!=q->x)
     if(ind[q->x]) {
       if((ind[q->x]<ind[nod])&&(ind[q->x]<ic)) ic=ind[q->x];
     }
     else {
       t[q->x]=nod;
       adaugaMuchie(nod,q->x);
       biconex(q->x);
       if(mr[q->x]<im) im=mr[q->x];
       if((nod==ROOT)&&(id<n)) rc=1;
       if((mr[q->x]>=ind[nod])||(rc&&(nod==ROOT))) memoreazaComponenta(nod,q->x);
     }
    q=q->next;
  }
  mr[nod]=im<ic?im:ic;
}

void scrie() {
  lista *q;
  freopen("biconex.out","w",stdout);
  printf("%d\n",nc);
  for(int i=0;i<nc;i++) {
    q=comp[i];
    while(q) {
      printf("%d ",q->x);
      q=q->next;
    }
    printf("\n");
  }
  fclose(stdout);
}

int main() {
  citeste();
  biconex(ROOT);
  scrie();
  return 0;
}