Pagini recente » Cod sursa (job #1482083) | Cod sursa (job #25613) | Cod sursa (job #255261) | Cod sursa (job #615168) | Cod sursa (job #2890411)
#include <fstream>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
using Graph = vector<vector<int>>;
void VisitComponent(const Graph& graph, int node, vector<bool>& used) {
queue<int> q;
q.push(node);
used[node] = true;
while (!q.empty()) {
node = q.front();
q.pop();
for (const auto& other : graph[node]) {
if (!used[other]) {
used[other] = true;
q.push(other);
}
}
}
}
int Solve(const Graph& graph) {
vector<bool> used(graph.size(), false);
auto res = 0;
for (size_t i = 0; i < graph.size(); i += 1) {
if (!used[i]) {
res += 1;
VisitComponent(graph, i, used);
}
}
return res;
}
int main() {
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int nodes, edges;
fin >> nodes >> edges;
Graph graph(nodes);
for (int i = 0; i < edges; i += 1) {
int a, b;
fin >> a >> b;
graph[a - 1].push_back(b - 1);
graph[b - 1].push_back(a - 1);
}
auto res = Solve(graph);
fout << res << "\n";
return 0;
}