Pagini recente » Cod sursa (job #1032499) | Cod sursa (job #16549) | Rating Chirilus Antonie (TonyC205) | Cod sursa (job #2764485) | Cod sursa (job #372502)
Cod sursa(job #372502)
/*
* paduri de multimi disjuncte
* */
#include <fstream>
#define NMAX 100001
using namespace std;
int tata[NMAX], h[NMAX], n, nrc;
int root(int x){
int y=x,tmp;
while(tata[y])
y=tata[y];
while(x-y){
tmp=x;
x=tata[x];
tata[tmp]=y;
}
return y;
}
int main(){
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int m,i,j,ri,rj;
fin>>n>>m;
nrc=n;
for( ; m ;--m){
fin>>i>>j;
ri=root(i);
rj=root(j);
if(ri != rj){
if(h[ri]>h[rj])
tata[rj]=ri;
else
if(h[ri] < h[rj])
tata[ri] = rj;
else{
tata[ri]=rj;
h[rj]++;
}
nrc--;
}
}
fout<<nrc;
return 0;
}