Cod sursa(job #2857907)

Utilizator backleventeBack Levente backlevente Data 26 februarie 2022 16:28:21
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.68 kb
#include <fstream>
#include <vector>

using namespace std;

#define ll long long

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

struct element {
  bool seen = false;
  vector <ll> sz;
};

ll N, M;
vector <element> x;

void dfs(ll act){
  x[act].seen = true;
  for(auto &i : x[act].sz)
    if(!x[i].seen)
      dfs(i);
}

int main(){ 
  cin >> N >> M;

  x.resize(N + 1);

  for(ll i = 1, a, b; i <= M; ++i){
    cin >> a >> b;
    x[a].sz.push_back(b);
    x[b].sz.push_back(a);
  }

  ll component_nr = 0;
  for(ll i = 1; i <= N; ++i){
    if(!x[i].seen){
      component_nr++;
      dfs(i);
    }
  }

  cout << component_nr;

  return 0; 
}