La estructura Union-Find, también llamada Disjoint-set Union (abreviado DSU) es una estructura de datos utilizada para unir y encontrar subgrafos, este se puede aplicar en algoritmos como el de Kruskal, que busca crear un árbol en determinado grafo, con la funcionalidad de evitar la creación de ciclos.
En su implementación más común cada conjunto está representado por un árbol de datos en el que cada nodo tiene una referencia a su padre y el representante de cada conjunto es la raíz del árbol de ese conjunto.
Cada conjunto va a tener un representante que lo identifica, y las operaciones que debemos poder realizar eficientemente son:
La primera idea poco eficiente que suele surgir, es simplemente tener, para cada elemento, su representante (lo que facilita la función union), y que al intentar unir dos conjuntos con los elementos xx e yy, recorremos todos los elementos, y si su representante es el mismo que el representante de xx(pertenecen al mismo conjunto actualmente), entonces su representante pasa a ser el representante de y).
Una posible mejora, es, además de guardar el representante de cada elemento, para cada representante guardar una lista con los elementos de su conjunto. Luego, al unir xx con yy, recorremos el conjunto más chico de los que contienen al xx y al yy (mirando las listas de sus representantes), y agregamos todos sus elementos a la lista de yy, cambiamos sus representantes por el representante de yy, y vaciamos la lista del representante de xx
Podemos pensar que cada conjunto es un árbol! El representante será la raíz, saber la raíz de un árbol (o sea el representante de un conjunto) es ir yendo a los padres de cada elemento, y agregar el conjunto de representante rx al de representante ry, es decirle a rx que su padre es ry, que sería como colgar el árbol de rx de la raíz ry.
Si colgamos el árbol de menor tamaño al de mayor, como antes con las listas, haremos menos operaciones. Y si además de esto, al buscar el padre de un elemento recursivamente, lo actualizamos cuando encontremos la raíz, las alturas de los árboles se achican muchísimo, y al calcular el representante de un elemento dos veces por ejemplo, en la primera lo encontramos, se lo asignamos como padre, y luego al buscar el representante es subir una sola vez.
https://es.wikipedia.org/wiki/Estructura_de_datos_para_conjuntos_disjuntos#:~:text=Un algoritmo Unión-Buscar es,están en el mismo conjunto.