Pagini recente » Cod sursa (job #1423512) | Cod sursa (job #1282270) | Cod sursa (job #2979867) | Cod sursa (job #2678825) | Cod sursa (job #372492)
Cod sursa(job #372492)
/*
* 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(tata[x]){
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[i]>h[j])
tata[j]=i;
else
if(h[i] < h[j])
tata[i] = j;
else{
tata[i]=j;
h[i]++;
}
nrc--;
}
}
fout<<nrc;
return 0;
}