Cod sursa(job #651057)

Utilizator DanyDanIrimia Daniel Ionut DanyDan Data 19 decembrie 2011 17:36:17
Problema Parcurgere DFS - componente conexe Scor 15
Compilator c Status done
Runda Arhiva educationala Marime 0.98 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;
}