Estructura de datos para clases de equivalencia.

Question

Permitir $ e $ ser una relación de equivalencia definida a través de un conjunto $ s $ . El acceso a $ e $ es solo a través de las consultas del formulario $ m (s_1, s_2)= 1 $ Si $ s_1 $ y $ s_2 $ están en la misma clase y $ 0 $ de lo contrario. Computación $ M $ es costoso (por ejemplo, $ o (n ^ 2) $ ).

Estoy buscando una estructura de datos eficiente $ d $ que admite consultas del formulario "Dado $ s $ < / span>, hace $ d $ contiene un elemento $ s '$ en la misma clase de equivalencia que < Span Class="Math-contenedor"> $ s $ "?
Un enfoque ingenuo es buscar elemento por elemento en $ d $ y prueba, pero ¿hay otra solución?

Answer 1

Lo mejor que puede hacer es realizar un seguimiento de todas las equivalencias conocidas actualmente utilizando una estructura de datos de unión.Inicialmente, cada elemento está en grupo propio.Cada vez que encuentre que dos elementos son equivalentes, usted fusiona sus grupos (a través de una operación sindical).

Luego, lo mejor que puede hacer para responder a la consulta que su lista es enumerar sobre todos los grupos (que no sea el que contiene $ s $ ), encuentre unRepresentante $ x $ para cada grupo de este tipo, y prueba si $ s $ es equivalente a $ x $ .