Expliquer structure de données « Union-Find »

Fermé
kisame94 Messages postés 5 Date d'inscription dimanche 1 novembre 2015 Statut Membre Dernière intervention 20 novembre 2015 - Modifié par Strumpfette le 20/11/2015 à 10:59
bonjour,est ce que quelqu'un peut m'expliquer cette structure de données « Union-Find »
#include <vector>
using namespace std;
class disjoint_sets {
vector<size_t> parent;
size_t _set_nbr;
public:
disjoint_sets(size_t n):_set_nbr(n){
parent.reserve(n);
for(size_t i = 0;i<n;++i){
parent[i] = i;
}
}
size_t find(size_t x){
return x == parent[x] ? x : find(parent[x]);
}
bool merge(size_t x,size_t y) {
size_t px = find(x);
size_t py = find(y);
if(px==py) return false;
parent[px] = py;
this->_set_nbr--;
return true;
}
size_t getSetsCount() const {
return this->_set_nbr;
}
bool sameSet(size_t x,size_t y){
return find(x) == find(y);
}
};


merci d'avance.