Cod sursa(job #651194)

Utilizator FIIGLMFIIGherasimLupascuMiron FIIGLM Data 19 decembrie 2011 23:48:20
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.02 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,*q;
     FILE *fin,*fout;
     fin=fopen("dfs.in","r");
     fout=fopen("dfs.out","w");
     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");return;}
         p->info=y;
         p->next=L[x];
         L[x]=p;
       if(!(q=(node*)calloc(1,sizeof(node)))) {printf("eroare");return;}
         q->info=x;
         q->next=L[y];
         L[y]=q;
     }
     
     for(i=1;i<=N;i++) 
      if(!viz[i]) { nrcomp++;
                    DFS(i);
                    }
      fprintf(fout,"%d",nrcomp);
      fclose(fin);
      fclose(fout);
       
    return 0;
}