Pagini recente » Cod sursa (job #1462133) | Cod sursa (job #2716218) | Cod sursa (job #1498615) | Cod sursa (job #1806402) | Cod sursa (job #1666063)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin ("dfs.in");
ofstream fout ("dfs.out");
const int nmax = 1e5+5;
const int mmax = 2e5+5;
int n, m, dady[nmax], rang[nmax];
pair<int,int> v[mmax];
int Find(int node){
while(dady[node]!=node)node=dady[node];
return node;
}
void Union(int x, int y){
if(rang[x] > rang[y]) dady[y]=x;
else dady[x]=y;
if(rang[x]==rang[y]) rang[y]++;
}
void Kruskal(){
int rx, ry, conexe, nr=0, i;
for(i=1; i<=n; i++)
dady[i]=i;
for(i=1; i<=m; i++){
rx=Find(v[i].first);
ry=Find(v[i].second);
if(rx!=ry){
nr++;
Union(rx, ry);
}
}
conexe=n-nr;
fout << conexe;
}
int main(){
ios_base::sync_with_stdio(false);
int i;
fin >> n >> m;
for(i=1; i<=m; i++)
fin >> v[i].first >> v[i].second;
Kruskal();
fin.close();
fout.close();
return 0;
}