Pagini recente » Cod sursa (job #2149488) | Cod sursa (job #420766) | Cod sursa (job #496770) | Cod sursa (job #3040945) | Cod sursa (job #2227883)
#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;
const int bmax = 1<<19;
char buff[bmax];
int n, m, dady[nmax], poz=bmax-1;
pair<int,int> v[mmax];
int Find(int node){
while(dady[node]!=node)node=dady[node];
return node;
}
void Union(int x, int y){
dady[x]=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();
fout.close();
return 0;
}