Cod sursa(job #2794960)

Utilizator MihaelaDanilaDanila Mihaela MihaelaDanila Data 5 noiembrie 2021 18:48:02
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.33 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

int nodSursa;
int distante[100001];

class Graf {
private:
    int m_nrNoduri;
    vector<vector<int>> m_listAdiacenta;
    vector<int> viz;
public:
    void citire(){
        ifstream f("../dfs.in");
        vector<int> aux;
        int nrMuchii;

        f>>this->m_nrNoduri;
        this->m_listAdiacenta.assign(this->m_nrNoduri + 1, aux);

        f>>nrMuchii;

        for(int i=0; i<nrMuchii; i++){
            int x,y;
            f>>x>>y;
            this->m_listAdiacenta[x].push_back(y);
        }

        viz.assign(this->m_nrNoduri + 1, 0);
    }

    void prelucrare(int nod, int x){
        //cout<<nod<<"\n";
        distante[nod] = distante[x] + 1;
    }

    void BFS(int nod){
        int curent;
        queue<int> coada;
        int viz[this->m_nrNoduri+1];
        for(int i=1; i<=m_nrNoduri; i++){
            viz[i] = 0;
        }

        coada.push(nod);
        viz[nod] = 1;
        prelucrare(nod, nod);

        while(!coada.empty()){
            curent = coada.front();
            for(int i=0; i < this->m_listAdiacenta[curent].size(); i++){
                if(viz[this->m_listAdiacenta[curent][i]] == 0){
                    coada.push(this->m_listAdiacenta[curent][i]);
                    prelucrare(coada.back(),curent);
                    viz[this->m_listAdiacenta[curent][i]] = 1;
                }
            }
            coada.pop();
        }

    }
/*
    void prelucrareDFS(int nod){
        cout<<nod<<endl;
    }
*/
    void DFS(int nod){
        //prelucrareDFS(nod);

        viz[nod] = 1;

        for(int i=0; i<this->m_listAdiacenta[nod].size(); i++){
            if(viz[this->m_listAdiacenta[nod][i]] == 0){
                DFS(this->m_listAdiacenta[nod][i]);
            }
        }
    }

    void afisDrumuri() {
        ofstream g("../bfs.out");
        for(int i=1; i <= this->m_nrNoduri; i++){
            g<<distante[i] - 1<<" ";
        }
    }

    int numaraComponenteConexe(){
        int nr = 0;
        for(int nod = 1; nod <= this->m_nrNoduri; nod++){
            if(this->viz[nod] == 0){
                nr++;
                DFS(nod);
            }
        }

        return nr;
    }
};

int main() {
    ofstream out("../dfs.out");

    Graf g;

    g.citire();

    out<<g.numaraComponenteConexe();
    return 0;
}