Pagini recente » Cod sursa (job #247929) | Cod sursa (job #2693391) | Poke | Cod sursa (job #517815) | Cod sursa (job #3340915)
#include <bits/stdc++.h>
void dfs(unsigned int start, std::vector<std::vector<unsigned int>>& v, std::vector<unsigned char>& viz) {
viz[start] = 1;
for (unsigned int i = 0; i < v[start].size(); i++) {
unsigned int tmp = v[start][i];
if (!viz[tmp]) {
viz[tmp] = 1;
dfs(tmp, v, viz);
}
}
} // prin referentiere ar fi mai eficient...
int main(void) {
std::ios::sync_with_stdio(false);
std::ifstream in("dfs.in");
std::ofstream out("dfs.out");
in.tie(nullptr);
out.tie(nullptr);
unsigned int n;
unsigned long int m;
in >> n >> m;
std::vector<std::vector<unsigned int>> ad(n + 1);
std::vector<unsigned char> viz(n + 1);
for (unsigned long i = 1; i <= m; i++) {
unsigned int x, y;
in >> x >> y;
ad[x].push_back(y);
ad[y].push_back(x);
}
for (unsigned int i = 1; i <= n; i++) {
std::sort(ad[i].begin(), ad[i].end());
ad[i].erase(std::unique(ad[i].begin(), ad[i].end()), ad[i].end());
}
unsigned int cnt = 0;
for (size_t i = 1; i <= n; i++) {
if (!viz[i]) cnt++, dfs(i, ad, viz);
}
out << cnt;
in.close();
out.close();
return 0;
}