Cod sursa(job #1897947)

Utilizator firewavesBirsu Ion firewaves Data 1 martie 2017 19:22:30
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>
#include <vector>
#include <queue>


std::ifstream fin("dfs.in");
std::ofstream fout("dfs.out");
int main()
{
    int n, m;
    fin >> n >> m;
    std::vector<int> p[n + 1];
    std::vector<bool> v(n+1, false);
    int res;
    for(int i = 0 ; i < m; i++) {
        int x, y;
        fin>> x >> y;

        p[x].push_back(y);
        p[y].push_back(x);
    }

    for(int i = 0; i <n; i++) {
        if(v[i])
            continue;
        res++;
        std::queue<int> q;
        q.push(i);
        v[i] = true;

        while(!q.empty()) {
            int x = q.front();
            q.pop();
            for(int aux:p[x]) {
                if(!v[aux]) {
                    v[aux] = true;
                    q.push(aux);
                }
            }
        }
    }
    fout<<res;
    return 0;
}