Cod sursa(job #2857823)

Utilizator vladp1324Vlad Pasare vladp1324 Data 26 februarie 2022 13:31:13
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.69 kb
#include <bits/stdc++.h>
#define ll long long

using namespace std;

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

int n, m, cc;
vector < int > v[100001];
bool ver[100001];

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

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);

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