Datenstruktur für Äquivalenzklassen

Question

Lassen Sie $ E $ ein Äquivalenz-Relation sein, der über einem Set $ s $ definiert ist. Der Zugriff auf $ E $ ist nur über Abfragen des Formulars $ M (S_1, S_2)= 1 $ Wenn $ S_1 $ und $ s_2 $ in derselben Klasse und $ 0 $ Ansonsten. Computing $ M $ ist teuer (sagen Sie, $ O (n ^ 2) $ ). .

Ich suche nach einer effizienten Datenstruktur $ D $ Das unterstützt Abfragen des Formulars "Angegebene $ s $ < / span>, enthält $ d $ ein Element $ s '$ in derselben Äquivalenzklasse wie < Span-Klasse="Math-Container"> $ s $ "?
Ein naiver Ansatz ist das Suchen von Elementen nach Element in $ D $ und test, aber gibt es andere lösung?

Answer 1

Das Beste, was Sie tun können, ist, alle aktuell bekannten Äquivalenzen mit einer Gewerkschaftsdatenstruktur zu verfolgen.Zunächst ist jedes Element in der eigenen Gruppe.Wann immer Sie feststellen, dass zwei Elemente gleichwertig sind, verschmelzen Sie ihre Gruppen (über einen Gewerkschaftsbetrieb).

dann das Beste, was Sie tun können, um die Abfrage zu beantworten, die Sie auf der Liste beantworten, besteht darin, alle Gruppen aufzulisten (außer dem einzelnen, der $ S $ ) ist, finden Sie arepräsentativ $ x $ für jede solche Gruppe, und testen Sie, ob $ S $ entspricht $ x $ .