Bonjour,

Je n'arrive pas à bien comprendre la structure de données apellée : "Disjoint-set data structure"

Meme si elle est bien expliqué sur wikipedia - disjoint-set data structure ou un exemple d'implementation ici : LiteratePrograms Disjoint set



Ce que je ne comprends pas c'est l'opération de find, elle est partout décrite par
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
 
function Find(x)
     if x.parent == x
        return x
     else   
        return Find(x.parent)
Et c'est censé retourner la racine.
Mais le problème c'est :
* Comment on fait pour savoir si un élément se trouve dans la structure ou pas.
* On ne possède pas un pointeur vers tous les éléments, donc comment connaitre x.parent si on n'a pas de pointeur vers x...

Exemple, j'ai 3 liste A, B, C avec dedans des elements numérotés de 1 à n.
Si je faut A.find(1), je vois pas comment ca peut marcher.

Merci