Cod sursa(job #3216474)

Utilizator antonc27Anton Malmygin antonc27 Data 17 martie 2024 12:45:12
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.69 kb
#include <iostream>
#include <fstream>
#include <vector>

std::vector<std::vector<int>> graph;
std::vector<bool> visited;

void dfs(int curr) {
  visited[curr] = true;
  for (auto& next : graph[curr]) {
    if (!visited[next]) {
      dfs(next);
    }
  }
}

int main() {
  int N, M;
  std::ifstream input("dfs.in");
  input >> N >> M;

  graph.resize(N + 1);
  visited.resize(N + 1);
  
  int x, y;
  for (int i = 0; i < M; i++) {
    input >> x >> y;
    graph[x].push_back(y);
    graph[y].push_back(x);
  }
  
  int res = 0;
  for (int i = 1; i <= N; i++) {
    if (!visited[i]) {
      dfs(i);
      res++;
    }
  }

  std::ofstream output("dfs.out");
  output << res << std::endl;
  return 0;
}