Cod sursa(job #2486229)

Utilizator LuciBBadea Lucian LuciB Data 2 noiembrie 2019 15:20:24
Problema Parcurgere DFS - componente conexe Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.55 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
vector <int> g[100001];
bool f[100000];
int n, m;
void dfs(int u){
  int i, v;
  f[u]=true;
  for(i=0; i<g[u].size(); i++){
    v=g[u][i];
    if(!f[v])
      dfs(v);
  }
}
int main(){
  int a, b, cnt;
  fin>>n>>m;
  for(int i=0; i<m; i++){
    fin>>a>>b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  cnt=0;
  for(int i=1; i<=n; i++){
    if(!f[i]){
      dfs(i);
      cnt++;
    }
  }
  fout<<cnt;
  return 0;
}