Estrutura de dados para classes de equivalência

Question

Deixe $ E $ ser uma relação de equivalência definida sobre um conjunto $ s $ . O acesso a $ E $ é apenas via consultas da forma $ m (s_1, s_2)= 1 $ Se $ s_1 $ e $ s_2 $ estão na mesma classe e $ 0 $ de outra forma. Computação $ M $ é caro (digamos, $ O (n ^ 2) $ ).

Eu estou procurando uma estrutura de dados eficiente $ D $ que suporta consultas do formulário "dado $ S $ < / span>, $ D $ contém um elemento $ s '$ na mesma classe de equivalência como < Span Class="contêiner matemática"> $ S $ "?
Uma abordagem ingênua é procurar elemento por elemento na $ D $ e teste, mas existe outra solução?

Answer 1

O melhor que você pode fazer é acompanhar todas as equivalências atualmente conhecidas usando uma estrutura de dados da Union-Encontrar.Inicialmente, cada elemento está em grupo próprio.Sempre que você achar que dois elementos são equivalentes, você mescla seus grupos (através de uma operação da União).

Então, o melhor que você pode fazer para atender a lista da qual sua lista é enumerar em todos os grupos (diferente do que contém $ S $ ), encontrar umrepresentante $ x $ para cada grupo, e teste se $ s $ é equivalente a $ x $ .