Cod sursa(job #2245805)

Utilizator skoda888Alexandru Robert skoda888 Data 25 septembrie 2018 21:25:40
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb

#include <iostream>
#include <fstream>
#include <vector>


void DFS(std::vector<int> _graf[], bool viz[], int nod)
{
    for(int i = 0; i < _graf[nod].size(); ++i){
        if(!viz[_graf[nod][i]]){
            viz[_graf[nod][i]] = true;
            DFS(_graf, viz, _graf[nod][i]);
        }
    }
}

int main(){
    std::ifstream in("dfs.in");
    std::ofstream out("dfs.out");
    int N;
    int M;

    in >> N >> M;
    std::vector<int> graf[N + 1];
    bool viz[N + 1] = {};

    for(int i = 1; i <= M; ++i){
        int x;
        int y;
        in >> x >> y;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }

    int num_comp_conexe = 0;
    for(int i = 1; i <= N; ++i){
        if(!viz[i]){
            ++num_comp_conexe;
            viz[i] = true;
            DFS(graf, viz, i);
        }
    }
    out << num_comp_conexe;

    return 0;
}