Cod sursa(job #2923977)

Utilizator Luca_Miscocilucainfoarena Luca_Miscoci Data 22 septembrie 2022 09:37:42
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.67 kb
#include <fstream>
#include <vector>

using namespace std;

#define NMAX 10000
vector <int> graf[NMAX + 1];
bool viz[NMAX + 1];

void dfs (int node){

  viz[node] = 1;
  int _size = graf[node].size();
  for (int i = 0; i < _size; i++){
    if (!viz[graf[node][i]])
      dfs (graf[node][i]);
  }
}

int main(){

  ifstream fin ("dfs.in");
  ofstream fout ("dfs.out");

  int n, m, a, b;

  fin >> n >> m;

  int sol = 0;
  for (int i = 0; i < m; i++){
    fin >> a >> b;
    graf[a].push_back(b);
    graf[b].push_back(a);
  }

  for (int i = 0; i < n; i++){
    if (!viz[i]){
      sol++;
      dfs(i);
    }
  }

  fout << sol;
  return 0;
}