Cod sursa(job #2789295)

Utilizator anaop32Oprea Ana-Maria anaop32 Data 27 octombrie 2021 12:40:20
Problema Parcurgere DFS - componente conexe Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <bits/stdc++.h>
using namespace std;


void DFS(int nod, vector<vector<int>> listaVecini, vector<int> &vizitat){
    vizitat[nod] = 1; // vizitez nodul curent
    // pentru fiecare vecin al nodului curent
    for (auto i : listaVecini[nod]){
        if (vizitat[i - 1] == 0){ // daca nu e vizitat atunci facem dfs pe el (avem i-1 pentru ca indicii pornesc de la 0 dar nodul meu e numerotat de la 1)
            DFS(i - 1, listaVecini, vizitat);
        }
    }
}

int main(){
    ifstream f("dfs.in");
    ofstream g("dfs.out");

    int n, // nr noduri 
        m, // nr muchii  
        muchie1, // primul nod al muchiei
        muchie2, // al doilea nod al muchiei
        nrComponenteConexe = 0;
    vector<vector<int>> listaVecini; // lista de vecini al grafului
    vector<int> vizitat; // vector care retine daca un nod a fost vizitat sau nu

    f >> n >> m;

    // pun in lista de vecini un vector care are pe prima pozitie nodul respectiv
    for (int i = 1; i <= n; i++){
        vector <int> aux;
        aux.push_back(i);
        listaVecini.push_back(aux);
    }

    // construiesc vectorul vizitat si pun pe fiecare pozitie 0 (niciun nod nu a fost vizitat inca)
    for (int i = 0; i < n; i++){
        vizitat.push_back(0);
    }

    // construire lista de vecini
    for (int i = 0; i < m; i++){
        f >> muchie1;
        f >> muchie2;
        listaVecini[muchie1 - 1].push_back(muchie2);
        listaVecini[muchie2 - 1].push_back(muchie1);
    }

    // numarul de nrComponenteConexe = cand gasesc un nod care nu a fost inca vizitat dupa ce am facut dfs pe nodurile anterioare
    for(int i = 0; i < n; i++){
        if (vizitat[i] == 0){
            nrComponenteConexe ++;
            DFS(i, listaVecini, vizitat);
        }
    }

    g << nrComponenteConexe;


    return 0;
}