Cod sursa(job #280469)

Utilizator drag0shSandulescu Dragos drag0sh Data 13 martie 2009 13:26:13
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include <stdio.h>
#include <stdlib.h>

FILE *f=fopen("ctc.in","r"),*g=fopen("ctc.out","w");
#define nmax 100001

int n,nr,nrc;
int *a[nmax],*at[nmax],*componenta[nmax];
int postordine[nmax],viz[nmax];

void citire();
void dfs(int);
void dfst(int);
void afisare();

int main(){
  int i;
  citire();
   for(i=1;i<=n;i++)dfs(i);
  for(i=n;i>0;i--){
    if(viz[postordine[i]]){
      nrc++;
      componenta[nrc]=(int*)realloc(componenta[nrc],sizeof(int));
      componenta[nrc][0]=0;
      dfst(postordine[i]);
    }
  }
  //  printf("(%d)",nrc);
   afisare();
  
  fclose(f);
  fclose(g);
  return 0;
  
}

void citire(){
  int m;
  fscanf(f,"%d%d",&n,&m);
  int x,y,i;
  for(i=1;i<=n;i++){
    a[i]=(int*)realloc(a[i],sizeof(int));
    a[i][0]=0;
    at[i]=(int*)realloc(at[i],sizeof(int));
    at[i][0]=0;
  } 
  for(i=1;i<=m;i++){
    fscanf(f,"%d%d",&x,&y);
    a[x][0]++;
    a[x]=(int*)realloc(a[x],sizeof(int)*(a[x][0]+1));
    a[x][a[x][0]]=y;

    at[y][0]++;
    at[y]=(int*)realloc(at[y],sizeof(int)*(at[y][0]+1));
    at[y][at[y][0]]=x;
    }
}


void dfs(int x){
  viz[x]=1;
  int i;
  for(i=1;i<=a[x][0];i++)
    if(!viz[a[x][i]])dfs(a[x][i]);
  postordine[++nr]=x;    
}

void dfst(int x){
  viz[x]=0;
  int i;
  componenta[nrc][0]++;
  componenta[nrc]=(int*)realloc(componenta[nrc],sizeof(int)*(componenta[nrc][0]+1));
  componenta[nrc][componenta[nrc][0]]=x;
   for(i=1;i<=at[x][0];i++)
    if(viz[at[x][i]])dfst(at[x][i]);
}

void afisare(){
  int i,j;
  fprintf(g,"%d\n",nrc);
  for(i=1;i<=nrc;i++){
    for(j=1;j<=componenta[i][0];j++)
      fprintf(g,"%d ",componenta[i][j]);
    fprintf(g,"\n");
  }
}