Cod sursa(job #256371)

Utilizator Sorin_IonutBYSorynyos Sorin_Ionut Data 11 februarie 2009 17:39:58
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <stdio.h>

#define MAX 100002
#define IN "ctc.in"
#define OUT "ctc.out"

FILE *fin=fopen(IN,"r");
FILE *fout=fopen(OUT,"w");

struct nod
{
 int a;
 nod *x;
}*l1[MAX],*l2[MAX],*comp[MAX];
int post[MAX],n,m,cnt;
char v[MAX];

void df1(int);
void df2(int);

int main()
{
 fscanf(fin,"%d%d",&n,&m);
    
 nod *q;
 int A,B,i;
 
 for(i=1;i<=m;++i)
 {
  fscanf(fin,"%d%d",&A,&B);
  q=new nod;
  q->a=B;
  q->x=l1[A];
  l1[A]=q;    

  q=new nod;
  q->a=A;
  q->x=l2[B];
  l2[B]=q;    
 }  
 fclose(fin); 

 for(i=1;i<=n;++i)
  if(v[i]==0)
   df1(i);

 for(i=n;i>0;--i) 
  if(v[post[i]]==1)
  {
   ++cnt;
   df2(post[i]);
  }    
    
  fprintf(fout,"%d\n",cnt);
  
  for(i=1;i<=cnt;++i,fprintf(fout,"\n"))
   for (q=comp[i];q;q=q->x)
    fprintf(fout,"%d ",q->a);
    
 fclose(fout);       
 return 0;
}

void df1(int nodd)
{
 nod *q;
 v[nodd]=1;
 
 for(q=l1[nodd];q;q=q->x) 
  if(v[q->a]==0)
   df1(q->a);     
   
 post[++post[0]]=nodd;
}

void df2(int nodd)
{
 nod *q;   
 v[nodd]=0;
 
 q=new nod;
 q->a=nodd;
 q->x=comp[cnt];
 comp[cnt]=q;
      
 for(q=l2[nodd];q;q=q->x) 
  if(v[q->a]==1)
   df2(q->a);     
}