Cod sursa(job #651283)

Utilizator FIIHapauRocaRoca Maria-Magdalena FIIHapauRoca Data 20 decembrie 2011 01:56:11
Problema Componente tare conexe Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.31 kb
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define max 10001

typedef struct node
{int info;
struct node *next;}node;

node *graf[max], *graft[max], *rez[max] , *nod;

int n, m, viz[max], postviz[max], l=0, nr;

FILE *f;FILE *h;

void add(node *p, int s)
{node *nod;
nod=(node *)malloc(sizeof(node));
nod->next=p;
nod->info=s;
p=nod;}

void df(int k)
{node *p;
viz[k]=1;
for (p=graf[k]; p; p=p->next)
   if (!viz[p->info])
       df(p->info);
postviz[++l]=k;}
 
void dft(int k)
{node *p;
viz[k]=0;
add(rez[nr], k);
for (p=graft[k]; p; p=p->next)
   if (viz[p->info])
       dft(p->info);
}
 
void afisare ()
{node *p;
int index;   
fprintf (h,"%d\n",nr);
for (index=1; index<=nr; ++index)   
 {for (p=rez[index]; p; p=p->next)        
   fprintf (h,"%d ",p->info);   
  fprintf (h,"\n");}
}

int main()
{int index;
int x, y;
f=fopen("ctc.in","r");
h=fopen("ctc.out","w");
fscanf(f,"%d%d",&n,&m);

for (index=0; index<m; ++index)
         {fscanf(f,"%d %d",&x,&y);
          add(graf[x],y);
          add(graft[y],x);}
 
for (index=0; index<n; ++index)
       if (!viz[index])
          df(index);
for (index=n; index; --index) 
      if (viz[postviz[index]])
         {++nr;
          dft(postviz[index]);}
afisare();
fclose(f);fclose(h);free(nod);
return 0;}