Struttura dei dati per le classi di equivalenza

Question

Let $ E $ essere una relazione di equivalenza definita su un set $ s $ . L'accesso a $ E $ è solo tramite query del modulo $ m (s_1, s_2)= 1 $ se $ s_1 $ e $ s_2 $ sono nella stessa classe e $ 0 $ altrimenti. Computing $ m $ è costoso (ad esempio, $ o (n ^ 2) $

).

). Sto cercando una struttura dati efficiente $ d $ che supporta le query del modulo "data $ s $ s < / span>, $ d $ contenere un elemento $ s '$ nella stessa classe di equivalenza di < Span Class="Math-Container"> $ s $ "?
Un approccio ingenuo è quello di cercare elemento per elemento in $ d $ e test, ma c'è altre soluzione?

Answer 1

Il meglio che puoi fare è tenere traccia di tutte le equivalenze attualmente note utilizzando una struttura dati di ritrovamento Unione.Inizialmente, ogni elemento è nel proprio gruppo.Ogni volta che trovi che due elementi sono equivalenti, si unisci ai loro gruppi (tramite un'operazione dell'Unione).

Quindi, il meglio che puoi fare per rispondere alla query che l'elenco è quello di enumerare su tutti i gruppi (diverso da quello contenente $ s $ ), trovare aRappresentante $ x $ per ciascuno di tale gruppo e verificare se $ s $ equivalente a $ x $ .