Cod sursa(job #2924806)

Utilizator iulia.talpalariuIulia-Georgiana Talpalariu iulia.talpalariu Data 11 octombrie 2022 09:30:30
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
//#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
ifstream fileIn("dfs.in");
ofstream fileOut("dfs.out");


class Graf {
    int N;
    int M;
    vector<vector<int>> lista_ad;

    public:
        void citire();
        void dfs(const int& nod, vector<int> &sel);
        int nr_comp_conexe();
};

void Graf:: citire() {
    int a, b;
    fileIn>> N >> M;
    // resize
    lista_ad.resize(N + 1);

    for(int i=1; i<= M; i++) {
            fileIn >> a >> b;
            //cout << a << b << "\n";
            lista_ad[a].push_back(b);
            lista_ad[b].push_back(a);

    }



}
void Graf:: dfs(const int& nod, vector<int> &sel) {
    sel[nod] = 1;
    for(auto vecin : lista_ad[nod]) {
        if(sel[vecin] == 0) {
            dfs(vecin, sel);
        }
    }
}
int Graf:: nr_comp_conexe() {
    int nr = 0;
    vector<int> sel(N + 1,0);

    for (int i = 1; i<= N; i++) {
        if(sel[i] == 0) {
            dfs(i, sel);
            nr ++;
        }
    }
    return nr;
}

int main()  {
    Graf my_graph;

    my_graph.citire();

    fileOut<< my_graph.nr_comp_conexe();


    return 0;



}