Cod sursa(job #2639297)

Utilizator abcabc123abc abc abcabc123 Data 1 august 2020 12:17:31
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.59 kb
#include <fstream>
#include <vector>

using namespace std;

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

int n, m, nrcc, x, y;
vector < int > ma[100001];
bool v[100001];

void dfs (int nod) {
  v[nod] = true;
  for (int i = 0; i < ma[nod].size (); i++)
    if (not v[ma[nod][i]])
      dfs (ma[nod][i]);
}

int main()
{
  fin >> n >> m;
  for (int i = 1; i <= m; i++) {
    fin >> x >> y;
    ma[x].push_back (y);
    ma[y].push_back (x);
  }
  for (int i = 1; i <= n; i++) {
    if (not v[i]) {
      dfs (i);
      nrcc++;
    }
  }
  fout << nrcc;
  return 0;
}