Cod sursa(job #2488857)

Utilizator bogdanvladmihaiBogdan Vlad-Mihai bogdanvladmihai Data 7 noiembrie 2019 18:28:42
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.62 kb
#include <bits/stdc++.h>

const int MAX_N = 100005;

int n, m;

std::vector <int> g[MAX_N];
std::vector <bool> visited(MAX_N);

void dfs(int u) {
  visited[u] = 1;
  for (int v : g[u]) {
    if (visited[v] == 0) {
      dfs(v);
    }
  }
}

int main() {
  int u, v, cnt =0;
  freopen("dfs.in", "r", stdin);
  freopen("dfs.out", "w", stdout);
  scanf("%d %d", &n, &m);
  while (m --) {
    scanf("%d %d", &u, &v);
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int i = 1; i <= n; ++i) {
    if (visited[i] == 0) {
      dfs(i);
      ++cnt;
    }
  }
  printf("%d\n", cnt);
  return 0;
}