Cod sursa(job #2813595)

Utilizator iustin.pericicaPericica Iustin iustin.pericica Data 6 decembrie 2021 23:21:09
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

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

class Graph{

private:
    vector< vector<int> > listaAdiacenta;
    vector<bool> vizitat;
    int n;
public:
    Graph(int n1) : n(n1){
        this->listaAdiacenta.resize(n1 + 1);
        this->vizitat.resize(n1 + 1);
        for(int i = 0;i<n1;++i)vizitat[i] = false;
    };

    void adaugMuchie(int deLa, int la){
        this->listaAdiacenta[deLa].push_back(la);
    }


    void dfs(int varf){
        vizitat[varf] = true;
        for (int p: listaAdiacenta[varf]) {
            if(!vizitat[p]){
                dfs(p);
            }
        }
    }


    int nrComponenteConexe(){

        int contor = 0;
        for(int i = 1;i<=n;++i){
            if(!vizitat[i]){
                ++contor;
                dfs(i);
            }
        }

        return contor;

    }

    void printGraph(){
        for (int i = 1; i <= n; i++)
        {
            // print the current vertex number
            cout << i << " ---> ";

            // print all neighboring vertices of a vertex `i`
            for (int v: listaAdiacenta[i]) {
                cout << v << " ";
            }
            cout << endl;
        }
    }

};

int main()
{
    int n, m;
    fin>>n>>m;
    Graph g(n);
    for(int i = 1;i<=m;++i){
        int a, b;
        fin>>a>>b;
        g.adaugMuchie(a, b);
        g.adaugMuchie(b, a);
    }
    fout<<g.nrComponenteConexe();
    //g.printGraph();

    return 0;
}