Pagini recente » Borderou de evaluare (job #3305721) | Cod sursa (job #3328403) | Borderou de evaluare (job #3111239) | Cod sursa (job #447908) | Cod sursa (job #3340913)
#include <bits/stdc++.h>
void dfs(unsigned int start, std::vector<std::vector<unsigned int>> v, std::vector<unsigned char>& viz) {
std::queue<unsigned int> q;
viz[start] = 1;
q.push(start);
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);
}
}
}
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 int> (m + 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 (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;
}