Pagini recente » Cod sursa (job #2803018) | Rating CNAI PETRUTA LAZAR FURDUI (CNAI_PETRUTA_LAZAR_FURDUI) | Istoria paginii runda/avram_iancu_1/clasament | Cod sursa (job #1463890) | Cod sursa (job #1755754)
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
class Graph {
public:
Graph(int num_nodes) : num_nodes_(num_nodes), ctc_counter_(0) {
edges_.resize(num_nodes_);
}
void AddEdge(int first_node, int second_node) {
edges_[first_node].push_back(second_node);
edges_[second_node].push_back(first_node);
}
void CalculateCtc() {
vector<bool> visited(num_nodes_, false);
for (int i = 0; i < num_nodes_; ++i) {
if (!visited[i]) {
Dfs(i, visited);
ctc_counter_++;
}
}
}
void Dfs(int node, vector<bool> &visited) {
visited[node] = true;
for (int i = 0; i < edges_[node].size(); ++i) {
int next_node = edges_[node][i];
if (!visited[next_node]) {
Dfs(next_node, visited);
}
}
}
int GetCtcCounter() const {
return ctc_counter_;
}
private:
vector<vector<int>> edges_;
int num_nodes_;
int ctc_counter_;
};
int main() {
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
int num_nodes, num_edges;
scanf("%d %d", &num_nodes, &num_edges);
Graph *g = new Graph(num_nodes);
for (int i = 0; i < num_edges; ++i) {
int first_node, second_node;
scanf("%d %d", &first_node, &second_node);
g->AddEdge(first_node - 1, second_node - 1);
}
g->CalculateCtc();
printf("%d\n", g->GetCtcCounter());
return 0;
}