Cod sursa(job #2382438)

Utilizator vcerneaCernea Victor vcernea Data 18 martie 2019 12:19:01
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.61 kb

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
int n, m, cont;
vector<int> adiac[100001];
bool viz[100001];

void dfs(int k) {
  for (int y = 0; y < adiac[k].size(); y++)
    if (!viz[adiac[k][y]]) {
      viz[adiac[k][y]] = 1;
      dfs(adiac[k][y]);
    }
}

int main() {
  int i, a, b;
  in >> n >> m;
  for (i = 1; i <= m; i++) {
    in >> a >> b;
    adiac[a].push_back(b);
    adiac[b].push_back(a);
  }
  for (i = 1; i <= n; i++) {
    if (!viz[i]) {
      ++cont;
      dfs(i);
    }
  }
  out << cont;
}