Efficient intersection of equivalence classes

Question

Having two equivalence relations, both as a union find data structure with the same number of elements, what is the most efficient way to find the equivalence relation that is the intersection of both relations?

For example, lets have $R_1=\{\{1,2,3\},\{4\}\}$ and $R_2=\{\{1\},\{2,3,4\}\}$. Then the intersection would be $R'=\{\{1\},\{2,3\},\{4\}\}$ as $2$ and $3$ are considered equivalent in both $R_1$ and $R_2$.

The "obvious" way would be $O(n^2)$ and test equivalence for each pair in each of the given relations. But maybe some property of the given union-find data structure would allow for better complexity?

As far as I know, even the canonical representative of a class is not necessary the same but depends on the sequence of class merges. (that was one approach I had in mind but did not really work out)

Answer 1

For each equivalence class $X$ of $R_1$, find the representatives of all elements of $X$ in $R_2$. This tells you how the elements of $X$ split in $R_1 \cap R_2$. (You might need to use some efficient data structures or algorithms beyond union-find.) Repeat for all other equivalence classes. Total running time is $\tilde{O}(n)$.