Cod sursa(job #2774732)

Utilizator etohirseCristi Cretu etohirse Data 12 septembrie 2021 16:40:56
Problema Parcurgere DFS - componente conexe Scor 35
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <iostream>
#include <fstream>
#include <vector>

std::fstream fin("dfs.in", std::ios::in);
std::fstream fout("dfs.out", std::ios::out);

const int mxN = 100005;

int n, m, ans;
bool viz[mxN];
std::vector<int>Muchii[mxN];

void dfs(int nod) {
    viz[nod] = 1;

    for (unsigned i = 0; i < Muchii[nod].size(); ++i) {
        int vecin = Muchii[nod][i];

        if (!viz[vecin]) {
            dfs(vecin);
        }
    }
}

int main(){
  fin >> n >> m;

  for (int i = 0; i < m; ++i) {
     int x, y;
     fin >> x >> y;
     Muchii[x].push_back(y);
     Muchii[y].push_back(x);
  }

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

  fout << ans << '\n';
  return 0;
}