Cod sursa(job #314192)

Utilizator mlazariLazari Mihai mlazari Data 10 mai 2009 20:35:52
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include<stdio.h>
#define NMAX 100003

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

int n,m,i,id=0,nc=0,index[NMAX],lowlink[NMAX],is[NMAX];
lista* v[NMAX];
lista *comp[NMAX];
lista *s=NULL,*q;

void push(lista* &lst,int nod) {
  lista *q=new lista;
  q->x=nod;
  q->next=lst;
  lst=q;
}

int pop(lista* &lst) {
  lista *q=lst;
  lst=lst->next;
  int rez=q->x;
  delete q;
  return rez;
}

void citeste() {
  int i,x,y;
  freopen("ctc.in","r",stdin);
  scanf("%d %d",&n,&m);
  for(i=1;i<=n;i++) {
    v[i]=NULL;
    is[i]=0;
    index[i]=-1;
  }
  for(i=0;i<m;i++) {
    scanf("%d %d",&x,&y);
    push(v[x],y);
  }
  fclose(stdin);
}

void tarjan(int nod) {
  int nd;
  index[nod]=lowlink[nod]=id;
  id++;
  push(s,nod);
  is[nod]=1;
  lista *q=v[nod];
  while(q) {
    if(index[q->x]==-1) {
      tarjan(q->x);
      if(lowlink[q->x]<lowlink[nod]) lowlink[nod]=lowlink[q->x];
    }
    else
     if(is[q->x])
      if(index[q->x]<lowlink[nod]) lowlink[nod]=index[q->x];
    q=q->next;
  }
  if(lowlink[nod]==index[nod]) {
    comp[nc]=NULL;
    do {
      nd=pop(s);
      push(comp[nc],nd);
    } while (nod!=nd);
    ++nc;
  }
}

int main() {
  citeste();
  for(i=1;i<=n;i++)
   if(index[i]==-1) tarjan(i);
  freopen("ctc.out","w",stdout);
  printf("%d\n",nc);
  for(i=0;i<nc;i++) {
    while(comp[i]) printf("%d ",pop(comp[i]));
    printf("\n");
  }
  fclose(stdout);
  return 0;
}