Es una estructura que almacena un conjuntos disconjuntos. Se utiliza principalmente para saber si dos nodos de un grafo tienen alguna conexión en común, y en general es muy útil para resolver este tipo de problemas. Además, ocupa menos memoria que la implementación de un grafo a través de una matriz de adjacencia o una lista de listas.
Se pueden realizar dos operaciones principales:
- Find: Devuelve como resultado el nodo padre del árbol donde se encuantra el nodo que pasamos como parámetro
- Union: Conecta los dos conjuntos independientes a los que pertenecen cada uno de los nodos que pasamos como parámetros
- Union find - C++