Cod sursa(job #2797895)

Utilizator pizzandreeaCiurescu Andreea pizzandreea Data 10 noiembrie 2021 18:43:41
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <iostream>
#include <fstream>
#include <vector>

#define MAX 100001

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

class Graf{
    public:
    //date membre
        vector <int> A[MAX];    //liste de adiacenta
        int mM, mN;
        int nrComp;     //nr comp conexe
        static bool viz[MAX];

        //constructor

        Graf(int N, int M){
            mN = N;
            mM = M;
            nrComp = 0;
        }

        void CitireG(){
            int x, y;

            for(int i = 1; i <= mM; i++){
                // citim muchiile
                fin >> x >> y;
                A[x].push_back(y);  //adaugam ambele noduri in lista celuilalt de adiacenta
                A[y].push_back(x);  //deoarece graful e neorientat
            }
        }
        void DFS(int start);

        void ComponenteConexe();
};

bool Graf :: viz[MAX] ={0};

void Graf :: DFS (int start){
    viz[start] = 1;
    // vizitam nodul din care plecam

    for(int i = 0; i < A[start].size(); i++){
        // parcurgem toti vecinii nodului start
        if(!viz[A[start][i]] ){
            // daca nu am mai vizitat acest vecin
            DFS(A[start][i]);
        }
    }
}


void Graf :: ComponenteConexe(){
    
    for(int i = 1; i <= mN; i++){
        if(!viz[i]){
            nrComp++;
            DFS(i);
        }
    }
}

int main(){
    int N, M;
    fin >> N >> M;
    Graf G(N,M);
    G.CitireG();
    G.ComponenteConexe();
    fout<<G.nrComp;

    return 0;
}