Union-Find (Disjoint Set)

Union-Find (también llamado Disjoint Set Union) es una estructura de datos que rastrea grupos de elementos. Soporta dos operaciones: find(x) devuelve el "representante" del grupo de x (qué grupo pertenece), y union(x, y) fusiona los grupos de x e y. La motivación: detectar si dos nodos están en el mismo componente conectado de un grafo sin hacer BFS/DFS cada vez. Con path compression y union by rank, ambas operaciones son prácticamente O(1) amortizado.

Union-Find es la estructura ideal para problemas de conectividad dinámica: a medida que se agregan aristas a un grafo, detectar cuándo dos nodos quedan conectados. El algoritmo de Kruskal para el árbol de expansión mínima usa Union-Find para verificar si agregar una arista crearía un ciclo. También se usa en el problema de "islas" (contar regiones conectadas en una matriz), en redes sociales (detectar comunidades), y en compiladores (alias analysis).

class UnionFind {
  #padre;
  #rango;
  #componentes;
  
  constructor(n) {
    this.#padre = Array.from({ length: n }, (_, i) => i);
    this.#rango = new Array(n).fill(0);
    this.#componentes = n;
  }
  
  // Find con path compression - O(α(n)) ≈ O(1)
  find(x) {
    if (this.#padre[x] !== x) {
      this.#padre[x] = this.find(this.#padre[x]); // Path compression
    }
    return this.#padre[x];
  }
  
  // Union by rank - O(α(n)) ≈ O(1)
  union(x, y) {
    const px = this.find(x), py = this.find(y);
    if (px === py) return false; // Ya están conectados
    
    if (this.#rango[px] < this.#rango[py]) {
      this.#padre[px] = py;
    } else if (this.#rango[px] > this.#rango[py]) {
      this.#padre[py] = px;
    } else {
      this.#padre[py] = px;
      this.#rango[px]++;
    }
    this.#componentes--;
    return true;
  }
  
  conectados(x, y) { return this.find(x) === this.find(y); }
  get numComponentes() { return this.#componentes; }
}

// Problema: Número de provincias
// n ciudades, isConnected[i][j]=1 si i y j están conectadas
function numProvincias(isConnected) {
  const n = isConnected.length;
  const uf = new UnionFind(n);
  
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (isConnected[i][j] === 1) uf.union(i, j);
    }
  }
  return uf.numComponentes;
}

// Problema: Detectar ciclo en grafo
function tieneCiclo(n, aristas) {
  const uf = new UnionFind(n);
  for (const [u, v] of aristas) {
    if (!uf.union(u, v)) return true; // Ya conectados → ciclo
  }
  return false;
}