Pagini recente » Cod sursa (job #3316422) | Cod sursa (job #3315508) | Cod sursa (job #3336980) | Cod sursa (job #3336349) | Cod sursa (job #3314602)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int height[100005], viz[100005], nodes[100005], x, y, n, m, cc;
int fnd(int x){
if(x==viz[x])return x;
return fnd(viz[x]);
}
void unite(int a, int b){
if(height[a]>height[b]){
viz[b]=a;
nodes[a]+=nodes[b];
}
else{
viz[a]=b;
nodes[b]+=nodes[a];
}
if(height[a]==height[b]){
height[b]++;
}
}
int main()
{
fin>>n>>m;
cc=n;
for(int i=1; i<=n; i++){
viz[i]=i;
height[i]=1;
nodes[i]=1;
}
for(int i=1; i<=m; i++){
fin>>x>>y;
int a=fnd(x), b=fnd(y);
if(a!=b){
unite(a, b);
cc--;
}
}
fout<<cc;
return 0;
}