Cod sursa(job #1705422)

Utilizator monicalegendaLegenda Monica monicalegenda Data 20 mai 2016 16:04:00
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <stdio.h>
#include <vector>
#include <string.h>
#include <iostream>
#include <fstream>
#include <queue>
 
#define NMAX 100005
bool visited[NMAX];
int n, m;
std::vector<int> neighbors[NMAX];

void bfs (int source) {
    std::queue<int> BFSQueue;
    BFSQueue.push(source);
    visited[source] = true;
    int node;

    while (!BFSQueue.empty()) {
        node = BFSQueue.front();
        BFSQueue.pop();
        for (unsigned int i = 0; i < neighbors[node].size(); i++) {
            if (!visited[neighbors[node][i]]) {
                BFSQueue.push(neighbors[node][i]);
                visited[neighbors[node][i]] = true;
            }
        }
    }
}   
 
int main() {
    std::ifstream fin("dfs.in");
    std::ofstream fout("dfs.out");
 
    int i, x, y;
 
    fin >> n >> m;
  
    for (i = 1; i <= m; i++) 
    {
        fin >> x >> y;
        neighbors[x].push_back(y);
        neighbors[y].push_back(x);
    }
 
    memset(visited, false, NMAX * sizeof(bool));
    int nrcomp = 0;
    for (i = 1; i <= n; i++) {
        if (!visited[i]) {
            nrcomp++;
            bfs(i);
        }
    }
    fout << nrcomp << "\n";
    return 0;
}