Cod sursa(job #2111532)

Utilizator OldpugAlex Ionescu Oldpug Data 22 ianuarie 2018 11:40:58
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <vector>
#include <cstdint>

#ifndef INFOARENA
#include <iostream>
#define inImpl std::cin
#define outImpl std::cout
#define debugWaitImpl std::cin.get(); std::cin.get();
#else
#include <fstream>
std::ifstream inImpl("dfs.in");
std::ofstream outImpl("dfs.out");
#define debugWaitImpl
#endif

#define in inImpl
#define out outImpl
#define debugWait debugWaitImpl

constexpr auto nMax = 100001;

bool seen[nMax];
std::vector<int32_t> graph[nMax];

void dfs(int32_t node) {
  seen[node] = true;
  for (auto i : graph[node])
    if (!seen[i])
      dfs(i);
}

int main() {
  int32_t n, m;
  in >> n >> m;

  for (auto i = 1; i <= m; ++i) {
    int32_t x, y;
    in >> x >> y;
    graph[x].push_back(y);
    graph[y].push_back(x);
  }

  int32_t num{};
  for (auto i = 1; i <= n; ++i)
    if (!seen[i]) {
      ++num;
      dfs(i);
    }

  out << num;
  debugWait
}