Cod sursa(job #2001440)

Utilizator Narniuss08Bogdan Anghelache Narniuss08 Data 16 iulie 2017 17:43:22
Problema Parcurgere DFS - componente conexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <iostream>
#include <fstream>
#include <vector>

std::ifstream fin("dfs.in");
std::ofstream fout("dfs.out");

const int DIM = 100000;

std::vector<int> vecin[DIM];
int vizitat[DIM], tata[DIM], nrComp;

void DFS(int s){
  vizitat[s] = 1;
  for(auto j : vecin[s]){
    if(!vizitat[j]){
      tata[j] = s;
      DFS(j);
    }
  }
}
int main(){
  int n, m;
  fin>>n>>m;

  for(int i = 1 ; i <= m ; i++){
    int x, y;
    fin>>x>>y;
    vecin[x].push_back(y);
    vecin[y].push_back(x);
  }

  for(int i = 1 ; i <= n ; i++){
    if(!vizitat[i]){
      nrComp++;
      DFS(i);
    }
  }
  fout<<nrComp<<"\n";
  return 0;

}