Pagini recente » Cod sursa (job #1920884) | Cod sursa (job #3137408) | Cod sursa (job #2256394) | Cod sursa (job #1587380) | Cod sursa (job #2158852)
//DSU
#pragma GCC optimize("03")
#include <bits/stdc++.h>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
int n, m, x, y, dad[100100], cnt;
bool viz[100100];
int find(int x){
return (x == dad[x] ? x : dad[x] = find(dad[x]));
}
void join(int x, int y){
dad[find(x)] = find(y);
}
int main(){
ios_base::sync_with_stdio(0);
in.tie(NULL);
in >> n >> m;
for(int i = 1; i <= n; i++)
dad[i] = i;
for(int i = 1; i <= m; i++){
in >> x >> y;
join(x, y);
}
for(int i = 1; i <= n; i++){
find(i);
if(!viz[dad[i]]){
cnt++;
viz[dad[i]] = 1;
}
}
out << cnt;
return 0;
}