Cod sursa(job #3316359)

Utilizator eva.gavriliuGavriliu Eva Mihaela eva.gavriliu Data 18 octombrie 2025 15:36:47
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.65 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int n,m;
vector<int> listaVecini[100001];
vector<bool> vizitat;
void dfs(int nod){
  vizitat[nod] = true;
  for(auto v: listaVecini[nod]){
    if(!vizitat[v]){
      dfs(v);
    }
  }
}
int main(){
  ifstream fin("dfs.in");
  ofstream fout("dfs.out");
  fin >> n>> m;
  vizitat.assign(n + 1, false);
  for(int i = 0;i<m;i++){
    int a,b;
    fin >> a >> b;
    listaVecini[a].push_back(b);
    listaVecini[b].push_back(a);
  }
  int cnt = 0;
  for(int i = 1; i<=n;i++){
    if(!vizitat[i]){
      cnt++;
      dfs(i);
    }
  }
  fout << cnt << "\n";
}