Cod sursa(job #1677425)

Utilizator TimoteiCopaciu Timotei Timotei Data 6 aprilie 2016 16:04:18
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <fstream>
#include <queue>
#include <vector>
#include <bitset>
#define pb push_back
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int n ,m, x, y, s, el_conex;
bitset <100005> viz;
vector <int> vecin[100005];
void read(){
  f >> n >> m;
  for(int i = 1; i <= m; ++i){
    f >> x >> y;
    vecin[x].pb(y);
    vecin[y].pb(x);
  }
}
void dfs(int x){
  viz[x] = 1;
  for(int i = 0; i < vecin[x].size(); ++i)
    if(!viz[vecin[x][i]]){
      viz[vecin[x][i]] = 1;
      dfs(vecin[x][i]);
  }
}
int main()
{
    read();
    for(int i = 1; i <= n; ++i)
     if(!viz[i]){
        el_conex++;
        dfs(i);
     }
    g << el_conex;
    return 0;
}