Cod sursa(job #2737517)

Utilizator bogdanvladmihaiBogdan Vlad-Mihai bogdanvladmihai Data 4 aprilie 2021 20:15:23
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.67 kb
#include <bits/stdc++.h>

using namespace std;

#define debug(x) cerr << #x << " = " << x << "\n";

ifstream in("dfs.in");
ofstream out("dfs.out");

const int max_n = (int)1e5 + 5;

int n, m;

vector<int> g[max_n];

bool visited[max_n];

void dfs(int u) {
  visited[u] = true;
  for (int v : g[u]) {
    if (!visited[v]) {
      dfs(v);
    }
  }
}

int main() {
  in >> n >> m;
  for (int i = 1; i <= m; i++) {
    int u, v;
    in >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  int cnt = 0;
  for (int i = 1; i <= n; i++) {
    if (!visited[i]) {
      cnt++;
      dfs(i);
    }
  }
  out << cnt << "\n";
  return 0;
}