Cod sursa(job #2817434)

Utilizator schizofrenieShallan Davar schizofrenie Data 13 decembrie 2021 17:53:56
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <array>
#include <fstream>
#include <vector>

constexpr size_t MAXN = 100000;

std::array<std::vector<int>, MAXN> edges;
std::array<bool, MAXN> vis;

void
dfs (int node) {
   vis[node] = true;
   for (int to: edges[node])
      if (!vis[to])
         dfs(to);
}

int
conexe (int n) {
   int ret = 0;

   for (int i = 0; i != n; ++ i)
      if (!vis[i]) {
         ++ ret;
         dfs(i);
      }

   return ret;
}

int main () {
   int n, m;
   std::ifstream f("dfs.in");
   std::ofstream g("dfs.out");
   f >> n >> m;
   for (int i = 0; i != m; ++ i) {
      int from, to;
      f >> from >> to;
      -- from, -- to;
      edges[from].emplace_back(to);
      edges[to].emplace_back(from);
   }

   g << conexe(n);
}