Cod sursa(job #2259304)

Utilizator alex.cojocaruAlex Cojocaru alex.cojocaru Data 13 octombrie 2018 11:26:28
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <iostream>
#include <stdio.h>
#include <vector>

#define NMAX 100000

using namespace std;

struct muchie {
  int nod ;
};

vector <muchie> mat [ NMAX + 1 ] ;
char folosit [ NMAX + 1 ] ;

void dfs (int i ) {
  folosit[i] = 1 ;
  for (muchie elem : mat[i] ) {
    if (folosit[elem.nod] != 1 ) {
      dfs (elem.nod) ;
    }
  }
}

int main() {

  FILE *fin, *fout ;
  fin = fopen ("dfs.in", "r" ) ;
  fout = fopen ("dfs.out", "w" ) ;
  int n, m, i, a, b, count ;
  fscanf (fin, "%d%d", &n, &m ) ;
  for (i = 0 ; i < m ; i++ ) {
    fscanf (fin, "%d%d", &a, &b ) ;
    mat[a].push_back({b}) ;
    mat[b].push_back({a}) ;
  }
  count = 0 ;
  for (i = 1 ; i <= n ; i++ ) {
    if (folosit[i] != 1 ) {
      dfs(i) ;
      count++;
    }
  }
  fprintf (fout, "%d", count ) ;
  return 0;
}