Pagini recente » Cod sursa (job #1865255) | Cod sursa (job #499797) | Cod sursa (job #2867949) | Cod sursa (job #1504374) | Cod sursa (job #3314583)
#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){
a=fnd(a);
b=fnd(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;
if(viz[x]!=viz[y]){
unite(x, y);
cc--;
}
}
fout<<cc;
return 0;
}