Cod sursa(job #1267583)

Utilizator AnesthesicChereches Sergiu Alexandru Anesthesic Data 20 noiembrie 2014 00:53:55
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
#define nmax 200005
#define pb push_back
#define p push

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

vector <int> v[nmax];
queue <int> q;

int n, m, x, y, i, elemente;
bool seen[nmax];

void bfs(int x){
    q.p(x);
    int current = q.front();
    while(!q.empty()){
        for(int j=0; j<v[current].size(); j++)
            if(!seen[v[current][j]]){
                seen[v[current][j]] = true;
                q.p(v[current][j]);
            }
            q.pop();
    }
}

int main(){
    fin >> n >> m;
    for(i=1; i<=m; i++){
        fin >> x >> y;
        v[x].pb(y);
        v[y].pb(x);
    }
    for(i=1; i<=n; i++){
        if(!seen[i]){
            bfs(i);
            elemente++;
        }
    }
    cout << elemente << "\n";
    return 0;
}