Solución de tiempo $O(\log n)$

Obviando las soluciones muy elementales, que requieren tiempo $O(n)$ para alguna de las dos operaciones, una solución sencilla es tener $n$ nodos, uno por cada elemento $v$, y que cada clase de equivalencia sea un árbol formado por los nodos de los elementos participantes. En estos árboles, los hijos apuntan a su padre, y la raíz es el representante de la clase. La operación $Find(v)$ consiste entonces en recorrer los ancestros sucesivos de $v$ hasta llegar a la raíz $x$, y entonces responder $x$. La operación $Union(x,y)$, para dos raíces $x$ e $y$, cuelga $x$ como un hijo más de $y$ (es decir, hace que $y$ sea el padre de $x$) o vice versa, eligiendo siempre colgar el árbol con menos nodos del árbol con más nodos (cada nodo conoce el tamaño de su subárbol, lo que es fácil de mantener cuando se le agrega otro subárbol como hijo).

--> imagen

Es fácil ver por inducción que, en los árboles resultantes, un árbol de altura $r$ tiene $v \ge 2^r$ nodos. Esto vale para los nodos iniciales, que definimos de altura $0$ y que contienen $2^0=1$ nodos. Ahora consideremos dos árboles de $v_1$ y $v_2$ nodos, y alturas $r_1$ y $r_2$, respectivamente. Por hipótesis inductiva se cumple que $v_1 \ge 2^{r_1}$ y $v_2 \ge 2^{r_2}$. Supongamos que $v_1 \le v_2$, por lo que el primer árbol se cuelga del segundo. El árbol resultante tiene entonces $v=v_1+v_2$ nodos y su altura es $r=\max(r_1+1,r_2)$. Si la altura es $r = r_1+1$, la tesis inductiva se cumple porque $v = v_1+v_2 \ge 2 v_1 \ge 2 \cdot 2^{r_1} = 2^{1+r_1} = 2^r$. Si, en cambio, la altura es $r = r_2$, la tesis inductiva se cumple porque $v = v_1 + v_2 \ge v_2 \ge 2^{r_2} = 2^r$.

Como un árbol tiene a lo más $n$ nodos, su altura no puede ser más de $\log_2 n$, por lo cual la operación $Find$ cuesta tiempo $O(\log n)$. Por otro lado, la operación $Union$ es $O(1)$.