Cod sursa(job #3196625)

Utilizator zamfiresqAlexandra Zamfirescu zamfiresq Data 24 ianuarie 2024 13:29:57
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <stack>


std::vector<std::vector<int> > listaAdiacenta;
std::vector<bool> vizitat;


// algoritm dfs
void DFS(int s){
    std::stack<int> stiva;
    stiva.push(s); // inseram nodul sursa in coada vida
    vizitat[s] = true; // marcam nodul sursa ca vizitat

    while(!stiva.empty()){
        int nodSursa = stiva.top();
        stiva.pop();

        for(int &nodDest : listaAdiacenta[nodSursa]){
            if(!vizitat[nodDest]){
                stiva.push(nodDest);
                vizitat[nodDest] = true; // marcam nodul muchiei ca vizitat
            }
        }
    }
}


int main(){

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

    int N, M;
    fin >> N >> M;


    vizitat.resize(N, false);
    listaAdiacenta.resize(N);

    for(int i = 0; i < M; i++){
        int x, y;
        fin >> x >> y;
        x--;
        y--;
        listaAdiacenta[x].push_back(y);
        listaAdiacenta[y].push_back(x);
    }

    fin.close();

    int nrConex = 0;
    for(int i = 0; i < N; i++){
        if(!vizitat[i]){
            DFS(i);
            nrConex++;
        }
    }

    fout << nrConex << "\n";
    fout.close();


    return 0;
}