Cod sursa(job #651198)

Utilizator FIIHapauRocaRoca Maria-Magdalena FIIHapauRoca Data 19 decembrie 2011 23:54:39
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.91 kb
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define max 100001
#define maxm max*(max-1)/2

FILE *f;FILE *h;
int n,m,v[max],nc;

typedef struct node 
{int info;
 struct node *next;
}node;

node *list[max];
node *nod;
void add(int x,int y)
{node *nod;
nod=(node *)malloc(sizeof(node));
nod->info=y;
nod->next=list[x];
list[x]=nod;}

void init()
{int index,x,y;
fscanf(f,"%d",&n);
fscanf(f,"%d",&m);
for(index=1;index<=m;index++)
 {fscanf(f,"%d %d",&x,&y);
  add(x,y);
  add(y,x);}
}
 

void dfs(int index)
{v[index]=1;
 node *nod;
 nod=list[index];
 while(nod) 
   {if(v[nod->info]==0) 
      dfs(nod->info);
    nod=nod->next;}
}

int main()
{int index;
nc=0;
f=fopen("dfs.in","r");
h=fopen("dfs.out","w");
init();
for(index=1;index<=n;index++)
   if(v[index]==0) 
       {dfs(index);
         nc++;}
fprintf(h,"%d",nc);
fclose(f);
fclose(h);
free(nod);
return 0;
};