Pagini recente » Cod sursa (job #2197169) | Cod sursa (job #691394) | Cod sursa (job #200322) | Cod sursa (job #2150827) | Cod sursa (job #2780170)
#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;
}