Pagini recente » Cod sursa (job #579924) | Cod sursa (job #1471296) | Cod sursa (job #1870042) | Cod sursa (job #2069716) | Cod sursa (job #3225328)
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
class Solutuion {
private:
size_t N;
size_t M;
vector<vector<size_t>> adj;
vector<bool> visited;
public:
explicit Solutuion(ifstream &in) {
in >> N >> M;
adj.resize(N + 1);
visited.resize(N + 1, false);
size_t node1, node2;
for (size_t i = 1; i <= M; i++) {
in >> node1 >> node2;
adj[node1].push_back(node2);
adj[node2].push_back(node1);
}
}
void dfs(size_t node) {
visited[node] = true;
for (auto neighbour : adj[node]) {
if (visited[neighbour])
continue;
dfs(neighbour);
}
}
size_t solve() {
bool done = false;
size_t num_conex = 0;
while (!done) {
done = true;
for (size_t node = 1; node <= N; node++)
if (!visited[node]) {
dfs(node);
num_conex++;
done = false;
}
}
return num_conex;
}
};
int main() {
ifstream in("dfs.in");
ofstream out("dfs.out");
out << Solutuion(in).solve();
in.close();
out.close();
return 0;
}