Cod sursa(job #2789540)

Utilizator Teodor_AxinteAxinte Teodor-Ionut Teodor_Axinte Data 27 octombrie 2021 17:10:43
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>

using namespace std;

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


class Graph{
private:
    vector<int>v[100010];
    bitset<100010> viz;
public:
    Graph();
    ~Graph();
    void add_edge(int,int);
    void dfs(int);
    int nr_connected_components(int );
};


Graph::Graph() {

}

Graph::~Graph() {

}

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

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

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




int main() {
    Graph G;
    int n,m;
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        fin>>x>>y;
        G.add_edge(x,y);
    }

    fout<<G.nr_connected_components(n);

    return 0;

}