Conjuntos disjuntos (union-find)

Hay un problema que aparece disfrazado en todos lados: ir uniendo elementos de a pares y poder preguntar, en cualquier momento, si dos quedaron conectados. Recalcular las componentes con un recorrido cada vez es carísimo. Union-find responde esa pregunta sin recorrer nada.

Dos operaciones: encontrar y unir

La estructura mantiene una partición: cada elemento pertenece a exactamente un conjunto y los conjuntos no se solapan. Expone dos operaciones: find, que devuelve el representante del conjunto de un elemento, y union, que fusiona los conjuntos de dos elementos.

Con eso alcanza para todo. Dos elementos están juntos si sus representantes coinciden; no hace falta listar el conjunto ni compararlo con nadie.

Un bosque guardado en un arreglo

La implementación es un bosque guardado en un arreglo: cada posición apunta a su padre y la raíz se apunta a sí misma. find sube por los padres hasta la raíz, que es el representante. union hace que una raíz apunte a la otra.

Escrita así es correcta pero puede degenerar. Una cadena de uniones desafortunada arma un árbol que es una lista, y cada find cuesta $O(n)$. Las dos optimizaciones que siguen existen para evitar exactamente eso.

Colgar el chico del grande

La primera es elegir quién cuelga de quién. En vez de colgar siempre la primera raíz de la segunda, se cuelga el árbol más chico del más grande, midiendo por altura estimada (rango) o por cantidad de elementos.

Colgar el chico del grande no aumenta la altura salvo empate, y mantiene la altura acotada por $O(\log n)$. Es una línea de código que ya convierte el peor caso lineal en logarítmico.

Comprimir el camino de vuelta

La segunda es la compresión de caminos: cuando find sube hasta la raíz, aprovecha el viaje y reengancha directo a la raíz todos los nodos que pasó. La próxima consulta sobre cualquiera de ellos es un salto.

Cada find deja la estructura mejor que como la encontró. Los árboles se aplanan solos con el uso, sin ninguna reorganización explícita.

Prácticamente constante, y por qué

Con las dos juntas, una secuencia de $m$ operaciones sobre $n$ elementos cuesta $O(m\,\alpha(n))$, donde $\alpha$ es la inversa de la función de Ackermann. Esa función crece tan despacio que para cualquier $n$ imaginable vale menos que 5.

En la práctica es tiempo constante amortizado, aunque no lo sea en sentido estricto. La diferencia entre la versión ingenua y la optimizada son unas pocas líneas y varios órdenes de magnitud.

Kruskal y todo lo que es agrupar por equivalencia

El uso más conocido es Kruskal: recorre las aristas de menor a mayor peso y agrega la arista sólo si une dos componentes distintas, que es exactamente find seguido de union. Sin union-find, detectar ese ciclo requeriría un recorrido por arista.

También sirve para componentes conexas en línea, agrupar elementos equivalentes, o etiquetar regiones de una imagen. La limitación es fuerte y conviene tenerla clara: no hay operación de separar. Los conjuntos sólo se fusionan.

Las dos optimizaciones, escritas

La estructura son dos arreglos y dos funciones, y casi todo el interés está en dos líneas.

class DisjointSet {
  private readonly parent: number[];
  private readonly size: number[];

  constructor(count: number) {
    this.parent = Array.from({ length: count }, (_, index) => index);
    this.size = new Array<number>(count).fill(1);
  }

  find(element: number): number {
    if (this.parent[element] !== element) {
      // compresión de caminos: al volver, todos apuntan directo a la raíz
      this.parent[element] = this.find(this.parent[element]!);
    }
    return this.parent[element]!;
  }

  union(a: number, b: number): boolean {
    const rootA = this.find(a);
    const rootB = this.find(b);
    if (rootA === rootB) return false; // ya estaban juntos

    // unión por tamaño: el chico cuelga del grande, así el árbol no crece
    if (this.size[rootA]! < this.size[rootB]!) {
      this.parent[rootA] = rootB;
      this.size[rootB]! += this.size[rootA]!;
    } else {
      this.parent[rootB] = rootA;
      this.size[rootA]! += this.size[rootB]!;
    }
    return true;
  }
}

La asignación adentro de find es la compresión de caminos: la recursión ya encontró la raíz, y al volver aprovecha para dejar a cada nodo del camino apuntando directo a ella. La próxima consulta sobre cualquiera de esos nodos cuesta un paso.

Y el if de union es la unión por tamaño: colgar siempre el árbol chico del grande. Sin esa línea, unir en el orden equivocado produce una cadena de largo $n$ y cada find la recorre entera.

Lo que puede y lo que no

Ese «no puede quitar» no es un detalle de implementación: es estructural. La compresión de caminos destruye la información de cómo se llegó a cada raíz, y sin ella no hay forma de saber qué se rompería al sacar una arista. Cuando hace falta quitar, el problema se llama conectividad dinámica y necesita estructuras bastante más complicadas, o se resuelve procesando las operaciones al revés, que suele ser el truco del ejercicio.

Cierre

Un arreglo de padres, colgar el árbol chico del grande y aplanar el camino en cada consulta. Con eso, preguntar si dos elementos están conectados y fusionarlos cuesta prácticamente $O(1)$ amortizado, a cambio de no poder deshacer una unión.