Pagini recente » Cod sursa (job #2990234) | Cod sursa (job #1945046) | Cod sursa (job #535490) | Cod sursa (job #389283) | Cod sursa (job #3122191)
#include <fstream>
#include <vector>
using namespace std;
using Graph = vector<vector<int>>;
void VisitComp(const Graph& graph, vector<bool>& visited, int node) {
visited[node] = true;
for (const auto& next : graph[node]) {
if (!visited[next]) {
VisitComp(graph, visited, next);
}
}
}
int CountComps(const Graph& graph) {
auto visited = vector<bool>(graph.size(), false);
auto comps = 0;
for (size_t i = 0; i < graph.size(); i += 1) {
if (!visited[i]) {
comps += 1;
VisitComp(graph, visited, i);
}
}
return comps;
}
int main() {
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int nodes, edges;
fin >> nodes >> edges;
auto graph = Graph(nodes);
for (auto 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 = CountComps(graph);
fout << res << "\n";
return 0;
}