Cod sursa(job #651181)

Utilizator FIIGLMFIIGherasimLupascuMiron FIIGLM Data 19 decembrie 2011 23:35:23
Problema Parcurgere DFS - componente conexe Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 0.87 kb
#include <stdio.h>
#include <stdlib.h>

 typedef struct node
 {
   int info;
   struct node *next;
  } node;
  node *L[100001];
  
  int viz[100001],N,M,nrcomp,i,x,y;
  
 void DFS(int x)
  { node *c;
    viz[x]=1;
    c=L[x];
    while(c)
    {  if(!viz[c->info]) DFS(c->info);
       c=c->next;
       }
  }
  int main()
  {  node *p;
     FILE *fin,*fout;
     fin=fopen("dfs.in","w");
     fout=fopen("dfs.out","r");
     fscanf(fin,"%d%d",&N,&M);
     
     for(i=1;i<=M;i++)
     { fscanf(fin,"%d%d",&x,&y);
       if(!(p=(node*)calloc(1,sizeof(node)))) printf("eroare");
       p->info=y;
       p->next=L[x];
       L[x]=p;
     }
     
     for(i=1;i<=N;i++) 
      if(!viz[i]) { nrcomp++;
                    DFS(i);
                    }
      fprintf(fout,"%d",nrcomp);
      fclose(fin);
      fclose(fout);
       
    return 0;
}