Data structure for equivalence classes

Question

Let $E$ be an equivalence relation defined over a set $S$. The access to $E$ is only via queries of the form $M(s_1,s_2) = 1$ if $s_1$ and $s_2$ are in the same class and $0$ otherwise. Computing $M$ is expensive (say, $O(n^2)$).

I am looking for an efficient data structure $D$ that supports queries of the form "given $s$, does $D$ contain an element $s'$ in the same equivalence class as $s$"?
A naive approach is to search element by element in $D$ and test, but is there other solution?

Answer 1

The best you can do is keep track of all currently known equivalences using a Union-Find data structure. Initially, each element is in own group. Whenever you find that two elements are equivalent, you merge their groups (via a Union operation).

Then, the best you can do to answer the query you list is to enumerate over all the groups (other than the one containing $s$), find a representative $x$ for each such group, and test whether $s$ is equivalent to $x$.