Pagini recente » Cod sursa (job #1361963) | Cod sursa (job #3268080) | Cod sursa (job #1862996) | Cod sursa (job #1231113) | Cod sursa (job #3262703)
#include <bits/stdc++.h>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
int n, m, start, nrCompConex;
vector<int> g[100005], ans[100005];
bitset<100005> used;
void dfs(int node) {
used[node] = true;
ans[nrCompConex].push_back(node);
for(auto nxt : g[node])
if(!used[nxt])
dfs(nxt);
}
int main() {
in >> n >> m;
int u, v;
for(int i = 1; i <= m; i++) {
in >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
/*
out << n << '\n';
for(int i = 1; i <= n; i++) {
for(auto elem : g[i])
out << elem << ' ';
out << '\n';
}
*/
for(int i = 1; i <= n; i++) {
if(!used[i]) {
nrCompConex++;
dfs(i);
sort(ans[nrCompConex].begin(), ans[nrCompConex].end());
}
}
out << nrCompConex << '\n';
/*
for(int i = 1; i <= nrCompConex; i++) {
for(auto elem : ans[i])
out << elem << ' ';
out << '\n';
}
*/
return 0;
}