Pagini recente » Cod sursa (job #2104350) | Cod sursa (job #957495) | Cod sursa (job #943787) | Cod sursa (job #2256289) | Cod sursa (job #2975638)
#include <cstdio>
#include <memory>
#include <vector>
using namespace std;
class Solver{
private:
void DFS(int k, const vector<vector<int>>& Graph, vector<bool> *used) {
(*used)[k] = true;
for (auto v: Graph[k])
if(!(*used)[v])
DFS(v, Graph, used);
}
int countCC(const vector<vector<int>>& Graph) {
int connectedComp = 0;
vector<bool> used((int)Graph.size());
for (int i = 0; i < (int)Graph.size(); ++i)
if (!used[i]) {
DFS(i, Graph, &used);
++connectedComp;
}
return connectedComp;
}
public:
Solver() {
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
}
~Solver() {
fclose(stdin);
fclose(stdout);
}
void execute() {
int N, M;
scanf("%d%d", &N, &M);
vector<vector<int>> Graph(N);
int from, to;
for (int i = 0; i < M; ++i) {
scanf("%d%d", &from, &to);
--from;
--to;
Graph[from].emplace_back(to);
Graph[to].emplace_back(from);
}
printf("%d", countCC(Graph));
}
};
int main() {
unique_ptr<Solver> s = make_unique<Solver>();
s->execute();
return 0;
}