Cod sursa(job #650699)

Utilizator FIIBarMazNeaFIIBarcanMaziluNeagu FIIBarMazNea Data 18 decembrie 2011 19:47:43
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.85 kb
#include<stdio.h>
#include<stdlib.h>
#define NMAX 100003
typedef struct Node{int info; struct Node *next;}Node;
Node *G[NMAX];
FILE *inf,*outf;
int viz[NMAX],N,M
;


void citire()
{
inf=fopen("dfs.in","r");
int i,z,y;
fscanf(inf,"%d %d",&N,&M);
for(i=1;i<=M;i++)
 {
  fscanf(inf,"%d %d",&z,&y);
  Node *p,*q;
  if(!(p=(Node*)malloc(sizeof(Node)))) return ;
  p->info=y;
  p->next=G[z];
  G[z]=p;
  if(!(q=(Node*)malloc(sizeof(Node)))) return ;
  q->info=z;
  q->next=G[y];
  G[y]=q;
 }

}

void Dfs(int x)
{
Node *p;
viz[x]=1;
for(p=G[x];p;p=p->next)
      if(!viz[p->info])
      {
      Dfs(p->info);
      }     
}


int main()
{
int i,nrcomp=0;

outf=fopen("dfs.out","w");
citire();

for(i=1;i<=N;i++)
    if(viz[i]==0) { nrcomp++; Dfs(i); }
fprintf(outf,"%d",nrcomp);

fclose(inf);
fclose(outf);
return 0;    
}