Pagini recente » Cod sursa (job #490030) | Cod sursa (job #832847) | Cod sursa (job #1768027) | Cod sursa (job #1354930) | Cod sursa (job #2610263)
#include <bits/stdc++.h>
#define FILE_I "dfs.in"
#define FILE_O "dfs.out"
class Task {
int n, m;
int no_cox = 0;
std::vector< std::vector< int>> adj;
public:
void solve() {
read();
fa();
print();
}
private:
void read() {
std::ifstream fin(FILE_I);
fin >> n >> m;
adj.resize(n + 1);
int x, y;
for (int i = 0; i < m; ++i) {
fin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
fin.close();
}
void fa() {
std::vector<int> vizitat(n + 1, 0);
for (int i = 1; i <= n; ++i) {
if (vizitat[i] == 0) {
++no_cox;
dfs(i, vizitat);
// std::cout << std::endl;
}
}
}
void dfs(int nod, std::vector<int> &vizitat) {
// std::cout << nod << " ";
vizitat[nod] = 1;
for (auto &x : adj[nod]) {
if (vizitat[x] == 0) {
dfs(x, vizitat);
}
}
}
void print() {
std::ofstream fout (FILE_O);
fout << no_cox;
fout.close();
}
};
int main() {
Task *t = new Task();
t->solve();
delete t;
return 0;
}