Structure de données pour les classes d'équivalence

Question

let $ E $ être une relation d'équivalence définie sur un ensemble $ s $ . L'accès à $ e $ est uniquement via des requêtes de la forme $ m (s_1, s_2)= 1 $ si $ s_1 $ et $ s_2 $ est dans la même classe et $ 0 $ sinon. Informatique $ m $ est cher (disons, $ o (n ^ 2) $

Je cherche une structure de données efficace $ d $ qui prend en charge les requêtes du formulaire "donné $ s $ < / span>, est-ce que $ d $ contient un élément s '$ dans la même classe d'équivalence que < Span Classe="Math-Conteneur"> $ S $ "?
Une approche naïve consiste à rechercher l'élément par élément dans $ d $ et test, mais y a-t-il une autre solution?

Answer 1

Le mieux que vous puissiez faire est de garder une trace de toutes les équivalences connues actuellement à l'aide d'une structure de données Union-Trouvez.Initialement, chaque élément est propre au groupe.Chaque fois que vous constatez que deux éléments sont équivalents, vous fusionnez leurs groupes (via une opération syndicale).

Ensuite, le meilleur que vous puissiez faire pour répondre à la requête que vous liste est d'énumérer sur tous les groupes (autre que celui contenant $ S $ ), trouver unReprésentant $ x $ pour chaque groupe de ce type et testez si $ s $ est équivalent à $ x $ .