Cod sursa(job #2646756)

Utilizator fredtuxFlorin Dinu fredtux Data 1 septembrie 2020 22:33:48
Problema Parcurgere DFS - componente conexe Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

int const maxM = 200000;

void dfs(vector<vector<int>> l, vector<bool> &viz, int pos);

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

  int n, m;
  fin >> n >> m;

  vector<vector<int>> l(n + 1);

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

  int comp = 0;
  vector<bool> viz(n + 1);

  for (unsigned int i = 1; i <= n; i++) {
    if (!viz[i]) {
      dfs(l, viz, i);
      comp++;
    }
  }

  fout << comp;

  return 0;
}

void dfs(vector<vector<int>> l, vector<bool> &viz, int pos) {
  viz[pos] = true;

  for (unsigned int i = 0; i < l[pos].size(); i++) {
    if (!viz[l[pos][i]]) {
      viz[l[pos][i]] = true;
      dfs(l, viz, l[pos][i]);
    }
  }
}