Cod sursa(job #2780170)

Utilizator serafimalex2001Serafim Alex serafimalex2001 Data 6 octombrie 2021 11:15:25
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <vector>

class Graph {
    std::vector<std::vector<int>> Ad;
    int nodes;
    int size;
    std::vector<bool> vis;
public:
    Graph(const std::vector<std::pair<int,int>> &ad, int nodes, int size,int directed);
    void DFS(int node);
    int getComponents();
};

Graph::Graph(const std::vector<std::pair<int,int>> &ad, int nodes, int size, int directed) : nodes(nodes), size(size) {
    Ad.resize(nodes+1);
    for(int i = 0; i<size; ++i){
        Ad[ad[i].first].push_back(ad[i].second);
        if(directed == 0)
            Ad[ad[i].second].push_back(ad[i].first);
    }
}

void Graph::DFS(int node){
    vis[node] = 1;
    for(int i = 0; i<Ad[node].size(); ++i)
        if(vis[Ad[node][i]] == 0){
            DFS(Ad[node][i]);
        }
}

int Graph::getComponents() {
    int ct = 0;
    vis.resize(nodes);
    std::fill(vis.begin(), vis.end(), 0);
    for(int i = 1;i <= nodes; ++i)
        if(vis[i] == 0){
            DFS(i);
            ct++;
        }
    return ct;
}


int main() {
    std::vector<std::pair<int,int>> Ad;
    int n,m,x,y;
    std::cin >> n >> m;
    for(int i = 0; i<m; ++i){
        std::cin >> x >> y;
        Ad.push_back({x,y});
    }
    Graph G(Ad,n ,m, 0);
    std::cout<<G.getComponents();
    return 0;
}