Cod sursa(job #2796675)

Utilizator Teodor_AxinteAxinte Teodor-Ionut Teodor_Axinte Data 8 noiembrie 2021 17:10:52
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <bits/stdc++.h>

using namespace std;

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

class Graf{
private:
    int n,m;
    static const int N=100010;
    vector<int> v[N];
    bitset <N> viz;

public:
    Graf();
    ~Graf();
    void add_edge(int,int);
    void dfs(int);
    void read_Graf();
    int nr_connected_components();
};

Graf::Graf() {

}

Graf::~Graf() {

}

void Graf::add_edge(int x, int y){
    v[x].push_back(y);
    v[y].push_back(x);
}

void Graf::dfs(int node){
    viz[node] = 1;
    for(auto it:v[node])
        if(!viz[it])
            dfs(it);
}

int Graf::nr_connected_components()  {
    int ct=0;
    for(int i=1;i<=this->n;i++)
        if(!viz[i]){
            dfs(i);
            ct++;
        }
    return ct;
}

void Graf::read_Graf(){
    int nr_noduri,nr_muchii;
    fin>>nr_noduri>>nr_muchii;
    this->n = nr_noduri;
    this->m = nr_muchii;

    for(int i=1;i<=m;i++){
        int x,y;
        fin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
}

int main(){
    Graf G;
    G.read_Graf();
    fout<<G.nr_connected_components();

    return 0;
}