Cod sursa(job #2782414)

Utilizator iustin.pericicaPericica Iustin iustin.pericica Data 12 octombrie 2021 13:14:58
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>

using namespace std;

struct nod{

nod *next;
int val;

};

class Graph{

private:
    nod *varfuri[100001];
    int nrVarfuri;
    int nrMuchii;
    int varfStart;
    bool vizitat[100001];

public:
    Graph(){
        for(int i = 0;i<100001;++i){
            vizitat[i] = 0;
        }
    }

void citire(){
    cin>>nrVarfuri>>nrMuchii;
    for(int i = 1;i<=nrMuchii;++i){
        int x, y;
        cin>>x>>y;
        nod *p = new nod;
        p->val = x;
        p->next = varfuri[y];
        varfuri[y] = p;

        p = new nod;
        p->val = y;
        p->next = varfuri[x];
        varfuri[x] = p;

    }
}

void afisare(){

    for(int i = 1;i<=nrVarfuri;++i){
        nod *p = varfuri[i];
        while(p){
            cout<<p->val<<" ";
            p = p->next;
        }
        cout<<endl;
    }

}

void dfs(int varf){

vizitat[varf] = 1;
nod *p = varfuri[varf];
while(p){
    if(!vizitat[p->val]){
        dfs(p->val);
    }
    p = p->next;
}

}

int nrComponenteConexe(){

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

return contor;

}



};

int main()
{
    Graph g;
    g.citire();
    //g.afisare();
    cout<<g.nrComponenteConexe();
    return 0;
}