Cod sursa(job #3150636)

Utilizator victorzarzuZarzu Victor victorzarzu Data 17 septembrie 2023 19:06:32
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.67 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>

using namespace std;
#define oo 0x3f3f3f3f

ifstream f("dfs.in");
ofstream g("dfs.out");
int n, m;
vector<int> graph[100001];
bool viz[100001];

void read() {
 f>>n>>m;
 int x, y;
 for(int i = 1;i <= m;++i) {
    f>>x>>y;
    graph[x].push_back(y);
    graph[y].push_back(x);
 }
}

void dfs(const int& x) {
  viz[x] = true;
  for(const auto& ngh : graph[x]) {
    if(!viz[ngh]) {
      dfs(ngh);
    }
  }
}

void solve() {
  int result = 0;
  for(int i = 1;i <= n;++i) {
    if(!viz[i]) {
      ++result;
      dfs(i);
    }
  }
  g<<result;
}

int main() {
  read();
  solve();
  return 0;
}