Entrevista técnica de código: ¿Cómo implementar Union-Find y rastrear componentes conectados?

Enunciado y alcance

Hay n nodos etiquetados de 0 a n - 1. Inicialmente, cada nodo es su propio componente conexo. Implementa UnionFind con estas operaciones:

• union(a, b) une los componentes que contienen a a y b. Devuelve True solo cuando realmente se fusionan dos componentes previamente distintos.
• connected(a, b) informa si los dos nodos pertenecen actualmente al mismo componente.
• count() devuelve el número actual de componentes conexos.

Esta versión permite n = 0, pero cualquier argumento de operación debe ser una etiqueta válida o lanzar IndexError. El problema base solo agrega conexiones; no elimina aristas y las llamadas provienen de un solo hilo. Por ejemplo, después de comenzar con n = 6 y fusionar (0, 1), (1, 2) y (3, 4), los tres componentes son {0, 1, 2}, {3, 4} y {5}. Fusionar (2, 4) deja dos componentes. Un union(0, 3) posterior debe devolver False sin decrementar el conteo nuevamente.

Este es un problema general de entrevista de estructuras de datos en ingeniería de software. Su caso de uso principal es un flujo incremental de conexiones intercaladas con muchas consultas de conectividad y conteo de componentes. Si todas las aristas llegan de una vez y quien llama necesita un único conteo de componentes, DFS o BFS suele ser más directo; reconocer esa distinción es parte de una respuesta sólida.

Qué evalúa el entrevistador

La primera señal es la selección del estado. Union-Find no conserva el grafo completo. Representa cada conjunto como un árbol de punteros al padre cuya raíz es el representante del conjunto y apunta a sí misma. En consecuencia, connected(a, b) puede comparar dos raíces en lugar de recorrer cada arista almacenada.

La segunda señal es si union enlaza únicamente raíces. Escribir parent[a] = b directamente puede mover un nodo interno debajo de otro nodo y corromper la representación de su componente original. La secuencia correcta encuentra root_a y root_b, confirma que difieren y une la raíz del árbol más pequeño a la raíz del árbol más grande. size tiene sentido únicamente en las raíces y controla el crecimiento del árbol.

La tercera señal es una explicación de la compresión de caminos en lugar de una plantilla memorizada. Esta implementación utiliza path halving: a medida que find avanza hacia arriba, cambia el padre del nodo actual por su abuelo. Ese nuevo padre sigue estando en el mismo árbol, por lo que la conectividad no cambia mientras que los caminos futuros se vuelven más cortos. La forma iterativa también evita fallas por profundidad de recursión en un camino largo.

Finalmente, el entrevistador verifica el invariante del conteo, la terminología de complejidad y la verificación. components comienza en n y disminuye solo después de que dos raíces diferentes se fusionan. Las uniones duplicadas y las auto-uniones no pueden cambiarlo. Con unión por tamaño y compresión de caminos juntas, las operaciones toman un tiempo amortizado de O(α(n)) sobre una secuencia, no un estricto peor caso de O(1) para cada llamada.

Preguntas de aclaración antes de responder

• ¿Las conexiones solo se agregan o también se pueden eliminar? Union-Find estándar maneja adiciones.

Después de una eliminación arbitraria de aristas, el bosque de padres no puede revelar si otras aristas aún conectan los extremos; eso requiere un método offline o una estructura de conectividad dinámica más avanzada.

• ¿Las consultas están intercaladas en línea (online) o se proporcionan todas las aristas por adelantado? Las consultas intercaladas de unión y

conectividad favorecen a Union-Find. Para un único conteo de componentes en un grafo estático, DFS/BFS con lista de adyacencia es más transparente y conserva las aristas reales.

• ¿Qué debe devolver union? Aquí informa si ocurrió una fusión. Ese booleano admite la detección

de ciclos directamente y garantiza que el conteo de componentes cambie exactamente una vez.

• ¿Cómo deben comportarse los nodos inválidos? Esta versión lanza IndexError. Una solución de programación competitiva puede omitir

la validación bajo un contrato de validez garantizada, pero los índices negativos de Python no deben referirse silenciosamente al final del arreglo en una implementación pública.

• ¿La API debe informar el tamaño del componente o enumerar sus miembros? El size de la raíz puede responder el tamaño en un tiempo

amortizado casi constante. Enumerar miembros todavía cuesta al menos el tamaño de la salida, y esta estructura base no mantiene listas de membresía.

• ¿Las llamadas pueden ser concurrentes? La implementación base muta parent dentro de find, por lo que incluso una

consulta de conectividad no es de solo lectura ni es segura para subprocesos (thread-safe). La concurrencia requiere un contrato de bloqueo o un algoritmo concurrente especializado de Union-Find.

Estructura de respuesta en 30 segundos

“Mantendré dos arreglos de longitud n: parent[x] apunta a un padre y size[root] almacena el tamaño del árbol de la raíz. Inicialmente, cada nodo es su propio padre y el conteo de componentes es n. find camina hacia una raíz y realiza path halving haciendo que cada nodo visitado apunte a su abuelo. union encuentra ambas raíces; si son iguales, devuelve False. De lo contrario, une la raíz del árbol más pequeño a la raíz del más grande, suma sus tamaños, decrementa el conteo de componentes y devuelve True. Enlazar dos raíces no puede crear un ciclo, y path halving solo cambia punteros dentro de un mismo conjunto, por lo que la conectividad se mantiene correcta. La inicialización es O(n); las operaciones posteriores son O(α(n)) amortizado con espacio O(n)”.

Análisis paso a paso en profundidad

Una representación directa asigna una etiqueta de componente a cada nodo. connected es una comparación de etiquetas, pero fusionar dos componentes requiere escanear todo el arreglo y reemplazar cada etiqueta antigua, haciendo que un solo union cueste O(n). Otro enfoque ingenuo utiliza árboles de punteros al padre pero une las raíces sin controlar sus tamaños. Un orden de unión adverso puede crear una cadena larga y degradar find.

El diseño recomendado mantiene tres elementos de estado:

1. parent[x] es el padre de x, y cada raíz de árbol satisface parent[root] == root.
2. size[root] es el conteo de nodos del componente de esa raíz; los valores desactualizados en nodos que no son raíz nunca se leen.
3. components es igual al número de raíces en el bosque de padres.

A continuación se muestra la implementación. _validate es breve y solo lo utiliza esta clase, por lo que permanece junto a su lugar de llamada en lugar de convertirse en un módulo de utilidades separado.

class UnionFind:
    def __init__(self, n: int) -> None:
        if n < 0:
            raise ValueError("n must be non-negative")
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n

    def _validate(self, x: int) -> None:
        if x < 0 or x >= len(self.parent):
            raise IndexError("node out of range")

    def find(self, x: int) -> int:
        self._validate(x)
        while x != self.parent[x]:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, a: int, b: int) -> bool:
        root_a = self.find(a)
        root_b = self.find(b)
        if root_a == root_b:
            return False

        if self.size[root_a] < self.size[root_b]:
            root_a, root_b = root_b, root_a

        self.parent[root_b] = root_a
        self.size[root_a] += self.size[root_b]
        self.components -= 1
        return True

    def connected(self, a: int, b: int) -> bool:
        return self.find(a) == self.find(b)

    def count(self) -> int:
        return self.components

La corrección se deduce en tres pasos. Inicialmente, cada nodo es la única raíz de un árbol de un solo nodo, por lo que el bosque tiene n árboles y se cumplen los tres invariantes. Path halving cambia el padre de x por el padre de su padre original. Ese abuelo permanece en el mismo camino hacia la raíz original, por lo que la operación no puede cruzar componentes ni cambiar la raíz devuelta por find(x).

Una unión modifica solo dos raíces. Raíces iguales significan que los nodos ya están conectados, por lo que no hay cambios de estado. Para raíces diferentes, apuntar root_b a root_a une dos árboles en uno y no puede crear un ciclo porque esas raíces pertenecían a árboles separados. El nuevo tamaño de la raíz es la suma de los tamaños de los árboles anteriores, y el conteo de raíces disminuye exactamente en uno. Por inducción, dos nodos están conectados si y solo si find devuelve la misma raíz, y count() siempre coincide con el recuento real de componentes.

La unión por tamaño garantiza que cada vez que la profundidad de un nodo aumenta debido a que se une todo su árbol, el tamaño de su nuevo componente al menos se duplica. Incluso sin compresión de caminos, la altura del árbol es como máximo O(log n). Combinado con path halving, una secuencia de m finds y unions después de la inicialización tiene el límite amortizado de O(m α(n)). La función inversa de Ackermann α crece extremadamente lento. “Tiempo amortizado casi constante” es una forma precisa de resumirlo en una entrevista; “estricto peor caso de O(1)” no lo es. Los dos arreglos usan un espacio de O(n), y el find iterativo usa un espacio de pila auxiliar de O(1).

El estado se puede rastrear con esta secuencia de operaciones:

n = 6                         count = 6
union(0, 1) -> True           count = 5
union(1, 2) -> True           count = 4
union(3, 4) -> True           count = 3
connected(0, 2) -> True
connected(0, 4) -> False
union(2, 4) -> True           count = 2
union(0, 3) -> False          count = 2

La verificación necesita más de un ejemplo. Cubre n = 0 sin una consulta, una auto-unión en n = 1, una unión duplicada, dos componentes separados unidos por un puente, un nodo aislado, uniones presentadas en órdenes opuestos y etiquetas no válidas -1 y n. Para grafos pequeños aleatorios, mantén una lista de adyacencia como oráculo. Después de cada inserción de arista, vuelve a calcular la conectividad y el conteo de componentes con BFS y compáralos paso a paso con Union-Find. Esta prueba diferencial detecta errores sutiles de conteo y de raíz.

Si se conocen de antemano todas las m aristas y quien llama solicita un solo conteo de componentes, DFS/BFS con lista de adyacencia usa tiempo y espacio O(n + m) y expresa la intención con claridad. Union-Find se justifica cuando las aristas llegan de forma incremental y las consultas se intercalan con las uniones, o cuando el algoritmo de Kruskal necesita probar si una arista no dirigida crearía un ciclo. El modelo de operación —no la mera presencia de un grafo— determina la elección.

Respuesta de muestra de alta calidad

“Primero confirmaré que las relaciones solo se agregan, que las consultas se intercalan con las adiciones y que union debe informar si ocurrió una fusión. Ese modelo de operación se adapta a Union-Find. Si se tratara de un solo conteo de componentes sobre un grafo estático, usaría DFS en su lugar.

Mi estado es parent, size en las raíces y el número actual de raíces en components. Cada nodo apunta inicialmente a sí mismo. find camina iterativamente hacia la raíz y hace que cada nodo visitado apunte a su abuelo, acortando el camino sin recursión. union obtiene ambas raíces. Raíces iguales devuelven False y no cambian el conteo. De lo contrario, la raíz del árbol más pequeño apunta a la raíz del árbol más grande, se suman sus tamaños y se decrementa el conteo.

La representación se mantiene como un bosque. Path halving solo apunta un nodo a un ancestro en el mismo árbol, y union conecta las raíces de dos árboles diferentes, por lo que ninguna operación crea un ciclo de padres. Cada unión exitosa convierte exactamente dos árboles en uno, lo que también demuestra el invariante del conteo.

Construir los arreglos cuesta O(n). Con unión por tamaño y path halving, find, conectividad y unión son de tiempo amortizado O(α(n)), con espacio O(n). Mis pruebas enfatizan que la auto-unión y la unión duplicada no cambien el conteo, unir dos componentes grandes mediante un puente, un nodo aislado, la estructura vacía y etiquetas negativas no válidas. También probaría diferencialmente casos pequeños aleatorios contra BFS”.

Errores comunes

• Asignar parent[a] = b directamente → a puede no ser una raíz, por lo que el árbol original puede dividirse o

convertirse en una cadena descontrolada → Encuentra ambas raíces y enlaza solo raíces.

• Adjuntar siempre el segundo árbol al primero → un orden adverso crea un camino largo → **Usa

el size o rank de la raíz para elegir la dirección.**

• Devolver solo parent[x] desde find → un padre no tiene que ser la raíz, por lo que la conectividad indirecta

se clasifica erróneamente → Sigue los punteros hasta una raíz que sea su propio padre.

• Decrementar components después de cada llamada a union → las uniones duplicadas y las auto-uniones llevan el

conteo por debajo de la realidad → Actualízalo solo cuando las raíces difieran.

• Actualizar el tamaño de la raíz antigua después de intercambiar raíces → los metadatos divergen del árbol real →

Elige primero la raíz padre final, luego enlaza y suma los tamaños de manera coherente.

• Afirmar un peor caso de O(1) por operación → la garantía es amortizada sobre una secuencia e

incluye la función inversa de Ackermann → Reporta O(α(n)) amortizado.

• Ignorar los índices negativos de Python → find(-1) accede al último nodo en lugar de fallar →

Valida ambos límites en una implementación pública.

• Usar Union-Find básico para la eliminación arbitraria de aristas → los punteros al padre no retienen caminos alternativos

tras una eliminación → Usa procesamiento de eliminaciones offline, Union-Find con rollback o una estructura de conectividad dinámica.

• Tratar connected como de solo lectura → path halving escribe en parent, creando condiciones de carrera bajo llamadas

concurrentes → Define la sincronización antes de elegir un bloqueo global, particionamiento o un algoritmo concurrente.

Preguntas de seguimiento y cómo manejarlas

Pregunta de seguimiento 1: ¿Cómo puede Union-Find detectar un ciclo en un grafo no dirigido?

Procesa las aristas (u, v) una a una. Si union(u, v) devuelve False, los extremos ya estaban conectados antes de la nueva arista, por lo que esa arista cierra un ciclo. Un resultado True solo une dos componentes previamente separados. Esta regla se aplica directamente a grafos no dirigidos. La detección de ciclos dirigidos necesita un método como DFS de tres colores o clasificación topológica.

Pregunta de seguimiento 2: ¿Qué pasa si quien llama necesita deshacer la unión más reciente?

Usa Union-Find con rollback. Mantén la unión por tamaño y guarda en una pila de historial el padre antiguo, el tamaño de la raíz y el conteo de componentes de cada cambio real antes de modificarlos. Deshacer restaura esos valores. La compresión de caminos normalmente se omite porque un solo find muta muchas entradas, inflando el registro de rollback y complicando los límites. La unión por tamaño por sí sola limita la altura a O(log n) y funciona bien con divide y vencerás sobre una línea de tiempo de operaciones offline.

Pregunta de seguimiento 3: ¿Qué pasa si las relaciones se pueden eliminar arbitrariamente?

El Union-Find estándar no puede responder a eliminaciones online arbitrarias. Si se conoce la secuencia completa de operaciones, ubica el intervalo activo de cada arista en un árbol de segmentos a lo largo del tiempo y recórrelo con Union-Find con rollback; las eliminaciones que solo ocurren al final también se pueden procesar hacia atrás como inserciones. La inserción, eliminación y consulta verdaderamente online y frecuentes requieren una estructura de conectividad totalmente dinámica más avanzada. Saber si las operaciones son offline es, por lo tanto, una aclaración definitoria del problema.

Pregunta de seguimiento 4: ¿Cómo devolverías el tamaño de un componente o todos sus miembros?

El tamaño ya se almacena en la raíz, por lo que size_of(x) = size[find(x)] mantiene el mismo límite amortizado. Listar los miembros no se puede recuperar únicamente a partir del tamaño de la raíz. Escanear todos los nodos y comparar raíces cuesta O(n α(n)); mantener conjuntos de miembros agrega costos de fusión y memoria. Escanear suele ser más simple para una exportación ocasional. La enumeración frecuente puede justificar una representación diferente.

Pregunta de seguimiento 5: ¿Cómo manejarías llamadas desde múltiples hilos?

El cambio correcto más pequeño es un mutex alrededor de find, union y connected, porque path halving escribe en el arreglo de padres. Es fácil de demostrar pero serializa todas las operaciones. Solo la contención medida justifica un diseño concurrente basado en compare-and-swap atómico, enlaces deterministas o particionamiento. Dicho diseño debe volver a demostrar la ausencia de ciclos en los punteros al padre y actualizaciones atómicas de tamaño y recuento de componentes; reemplazar arreglos con variables atómicas no es suficiente por sí solo.