Cod sursa(job #1700666)

Utilizator TincaMateiTinca Matei TincaMatei Data 10 mai 2016 22:46:43
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.01 kb
#include <stdio.h>
#define MAX_NODURI 100000
#define MAX_MUCHII 200000

int start[1+MAX_NODURI];
int last[1+MAX_NODURI];
int next[1+MAX_MUCHII*2];
int muchie[1+MAX_MUCHII*2];
int fol[1+MAX_NODURI];

void insertMuchie(int i, int a, int b) {
  if(start[a] == 0)
    start[a] = last[a] = i;
  else
    last[a] = next[last[a]] = i;
  muchie[i] = b;
}

void fill(int nod) {
  int i;
  fol[nod] = 1;
  i = start[nod];
  while(i != 0) {
    if(!fol[muchie[i]])
      fill(muchie[i]);
    i = next[i];
  }
}

int main() {
  int n, m, a, b, i, componente;
  FILE *fin = fopen( "dfs.in" , "r" );
  fscanf(fin, "%d%d", &n, &m);
  for(i = 1; i <= m; i++) {
    fscanf(fin, "%d%d", &a, &b);
    insertMuchie(2 * i - 1, a, b);
    insertMuchie(2 * i, b, a);
  }
  fclose( fin );

  componente = 0;
  for(i = 1; i <= n; i++)
    if(!fol[i]) {
      fill(i);
      componente++;
    }

  FILE *fout = fopen( "dfs.out" , "w" );
  fprintf(fout, "%d", componente);
  fclose( fout );
  return 0;
}