Cod sursa(job #1278788)

Utilizator andrei_r_97Radoi Andrei andrei_r_97 Data 29 noiembrie 2014 14:10:59
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.02 kb
#include <stdio.h>
#include <stdlib.h>

#define MAX_N 100000

int nodVizitat[MAX_N+1];

typedef struct lista {
  int nod;
  struct lista *urm;
} lista;

lista *g[MAX_N+1];

void adauga(int i, int j) {
  lista *p = malloc( sizeof(lista) );
  p -> nod = j;
  p -> urm = g[i];
  g[i] = p;
}

void citesteGraf(int muchii, FILE *in) {
  int i, a, b;
  for ( i = 1; i <= muchii; i++ ) {
    fscanf(in, "%d %d", &a, &b);
    adauga(a,b);
    adauga(b,a);
  }
}

void DFS(int nod) {
  lista *p;
  nodVizitat[nod] = 1;
  for ( p = g[nod]; p != NULL; p = p -> urm )
    if ( !nodVizitat[ p -> nod ] )
      DFS(p -> nod);
}

int main()
{
  FILE *in  = fopen("dfs.in","r");
  FILE *out = fopen("dfs.out", "w");

  int muchii, noduri;
  fscanf(in,"%d %d",&noduri,&muchii);
  citesteGraf(muchii,in);

  int i, contor = 0;
  for ( i = 1; i <= noduri; i++ ) {
    if ( !nodVizitat[i] ) {
      contor++;
      DFS(i);
    }
  }

  fprintf(out,"%d",contor);

  fclose(in);
  fclose(out);

  return 0;
}