Cod sursa(job #651045)

Utilizator FIIGLMFIIGherasimLupascuMiron FIIGLM Data 19 decembrie 2011 17:22:42
Problema Parcurgere DFS - componente conexe Scor 15
Compilator c Status done
Runda Arhiva educationala Marime 0.8 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct node{
 int info;
 struct node *next;
} node;
node *L[100001];

long long viz[100001],N,M;

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;
   long long i,nrcomp=0,k,j;
   FILE *fin,*fout;
   fin=fopen("dfs.in","r");
   fout=fopen("dfs.out","w");
   fscanf(fin,"%lld%lld",&N,&M);
   for(k=1;k<=M;k++)
   { fscanf(fin,"%lld%lld",&i,&j);
     if(!(p=(node*)calloc(1,sizeof(node)))) return;  //se adauga j in lista vecinilor lui i
     p->info=j;
     p->next=L[i];
     L[i]=p;
    }
   
   for(i=1;i<=N;i++)
   if(viz[i]==0) { nrcomp++; DFS(i); }
   fprintf(fout,"%lld",nrcomp);
   fclose(fin);
   fclose(fout);
  return 0;
}