Cod sursa(job #3340915)

Utilizator initrdIarto Paul initrd Data 17 februarie 2026 09:51:33
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <bits/stdc++.h>

void dfs(unsigned int start, std::vector<std::vector<unsigned int>>& v,  std::vector<unsigned char>& viz) {

  viz[start] = 1;

  for (unsigned int i = 0; i < v[start].size(); i++) {
    unsigned int tmp = v[start][i];
    if (!viz[tmp]) {
      viz[tmp] = 1;
      dfs(tmp, v, viz);
    }
  }

} // prin referentiere ar fi mai eficient...

int main(void) {

  std::ios::sync_with_stdio(false);
  std::ifstream in("dfs.in");
  std::ofstream out("dfs.out");

  in.tie(nullptr);
  out.tie(nullptr);

  unsigned int n;
  unsigned long int m;
  in >> n >> m;

  std::vector<std::vector<unsigned int>> ad(n + 1);
  std::vector<unsigned char> viz(n + 1);
  for (unsigned long i = 1; i <= m; i++) {
    unsigned int x, y;
    in >> x >> y;

    ad[x].push_back(y);
    ad[y].push_back(x);
  }

  for (unsigned int i = 1; i <= n; i++) {
    std::sort(ad[i].begin(), ad[i].end());
    ad[i].erase(std::unique(ad[i].begin(), ad[i].end()), ad[i].end());
  }

  unsigned int cnt = 0;
  for (size_t i = 1; i <= n; i++) {
    if (!viz[i]) cnt++, dfs(i, ad, viz);
  }

  out << cnt;

  in.close();
  out.close();

  return 0;
}