Cod sursa(job #2754781)

Utilizator laurentium1234Laurentiu Mihalcea laurentium1234 Data 26 mai 2021 15:26:58
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.69 kb
#include <iostream>
#include <fstream>
#include <vector>

void recursion(std::vector<int> adj[], std::vector<int> p, int node)
{
  for (auto neigh : adj[node]) {
    if (p[neigh] == 0) {
      p[neigh] = node;
      recursion(adj, p, neigh);
    }
  }
}


int main()
{
  std::ifstream in("dfs.in");
  std::ofstream out("dfs.out");

  int n, m, cc_count = 0;

  in >> n >> m;

  std::vector<int> adj[n + 1];
  std::vector<int> p(n + 1, 0);

  for (int i = 0, to, from; i < m; i++) {
    in >> from >> to;
    adj[from].push_back(to);
    adj[to].push_back(from);
  }

  for (int i = 1; i <= n; i++) {
    if (p[i] == 0) {
      cc_count++;
      recursion(adj, p, i);
    }
  }

  out << cc_count << std::endl;
}