Enunciado y contexto
Recibes n usuarios y q operaciones con marca de tiempo. add id u v agrega una relación no dirigida con un ID, remove id la elimina y ask u v pregunta si dos usuarios están conectados en ese momento. Cada relación se agrega y se elimina a lo sumo una vez, y todas las operaciones se conocen antes de producir las respuestas.
Devuelve una respuesta booleana para cada ask. Explica por qué disjoint-set union ordinario no puede procesar eliminaciones de forma segura, cómo mapear las vidas útiles de las relaciones en una línea de tiempo, cómo restaurar el estado y qué límites y complejidad importan. El objetivo es la conectividad dinámica offline, no actualizaciones online arbitrarias.
Qué está evaluando el entrevistador
- Si reconoces que el invariante monótono de union-find se rompe cuando desaparecen aristas.
- Si puedes representar cada arista como un intervalo de vida semiabierto
[add time, remove time). - Si puedes descomponer un intervalo en nodos de segment tree
O(log q). - Si puedes implementar DSU con rollback sin compresión de caminos y con unión por tamaño.
- Si puedes conectar instantáneas (snapshots), retornos de recursión y la corrección de las consultas.
Preguntas para clarificar primero
- ¿Se conocen todas las operaciones de antemano? Si las respuestas deben ser online, el enfoque de la línea de tiempo no aplica.
- ¿Tiene cada relación un ID único? Sin uno, la eliminación de aristas duplicadas es ambigua.
- ¿Es el grafo no dirigido? Un grafo dirigido necesita una estructura de alcanzabilidad diferente.
- ¿Puede agregarse un ID nuevamente después de haber sido eliminado? De ser así, cada período de vida necesita su propio intervalo.
- ¿Las consultas son solo de conectividad, o también de tamaño de componente, caminos más cortos o caminos reales?
Estructura de respuesta en 30 segundos
DSU ordinario puede fusionar componentes pero no puede eliminar una arista sin saber qué estructura debe dividirse. Yo recorrería las operaciones, crearía [add, remove) para cada arista y extendería una arista sin eliminación hasta q. Colocaría cada intervalo en un segment tree sobre el tiempo. Durante el DFS, aplicaría las aristas de un nodo, respondería consultas en las hojas y haría rollback a la instantánea de entrada al salir del nodo. El DSU con rollback evita la compresión de caminos y utiliza unión por tamaño, de modo que cada cambio se registra y el costo total es O(q log q log n) con O(n + q log q) de espacio.
Análisis detallado paso a paso
Paso 1: Identificar por qué falla DSU ordinario
DSU ordinario almacena el resultado de todas las fusiones vistas hasta el momento. Eliminar una arista puede dejar un componente conectado a través de otra arista o puede requerir dividir un árbol; los punteros a padres por sí solos no revelan el corte afectado. No existe una "unión inversa" segura.
Paso 2: Construir intervalos de vida útil de las aristas
Registra cada tiempo de add. Cuando aparezca su remove, cierra [add, remove); la forma semiabierta mantiene la arista fuera de la marca de tiempo de eliminación. Una arista que sigue abierta al final se convierte en [add, q).
Paso 3: Cubrir intervalos con un segment tree
Almacena un intervalo en los nodos del segment tree que lo cubren por completo. Un intervalo ocupa a lo sumo O(log q) nodos. Cada arista almacenada en un nodo es válida para todo el rango de tiempo del nodo, por lo que se fusiona una vez en lugar de en cada hoja.
Paso 4: Diseñar DSU con rollback
Mantén parent y size. find sigue a los padres sin compresión de caminos. union conecta la raíz más pequeña a la raíz más grande y añade el hijo modificado, la raíz y el tamaño anterior a una pila de historial. La unión por tamaño acota la altura del árbol a O(log n).
Paso 5: DFS con instantáneas y restauración
Guarda la longitud del historial al entrar, aplica las aristas del nodo y responde ask en una hoja. Después de que ambos hijos terminen, haz pop hasta la longitud guardada. Las aristas de los padres permanecen activas para el siguiente hijo, mientras que las aristas exclusivas del hijo no pueden filtrarse entre hermanos.
Paso 6: Estructura de la implementación
La implementación tiene cuatro fases: construir intervalos semiabiertos, agregar cada intervalo a un segment tree temporal, recorrer con un DSU con rollback y responder en las hojas. Los detalles críticos son no usar compresión de caminos, registrar el tamaño anterior del componente y restaurar exactamente a la instantánea.
Paso 7: Demostrar el invariante y la complejidad
Al entrar a un nodo del segment tree, DSU contiene exactamente las aristas activas a lo largo del rango de ese nodo más las aristas aplicadas por los ancestros. Las aristas de los hijos existen solo en el subárbol del hijo y se eliminan al retornar, por lo que una hoja ve exactamente la unión de aristas activas. Cada arista se almacena en O(log q) nodos y cada unión cuesta O(log n) con unión por tamaño, lo que da un tiempo de O(q log q log n) y un almacenamiento de O(n + q log q).
Paso 8: Comparar alternativas y casos de falla
Si las aristas solo llegan y se consulta la conectividad, DSU ordinario es más simple con operaciones amortizadas casi constantes. Las eliminaciones online verdaderas requieren una estructura de conectividad dinámica; el árbol de línea de tiempo no puede conocer una eliminación futura desconocida. DSU tampoco puede responder caminos más cortos, los cuales necesitan BFS, Dijkstra u otra estructura de caminos.
Respuesta de ejemplo de alta calidad
Primero confirmaría que cada operación se conoce y que cada relación tiene un ID estable. DSU ordinario solo fusiona, y la eliminación rompe su invariante de componentes, por lo que recorrería las operaciones para obtener vidas útiles de aristas semiabiertas y extendería las aristas aún abiertas hasta el final. Colocaría esos intervalos en un segment tree sobre el tiempo, fusionaría las aristas de los nodos durante el DFS, respondería la conectividad en las hojas y haría rollback a la longitud del historial de entrada al retornar. El DSU con rollback evita la compresión de caminos, usa unión por tamaño y registra cambios de padres y tamaños, dando una altura de árbol de O(log n). Cada arista aparece en O(log q) nodos, por lo que el tiempo es O(q log q log n) y el espacio es O(n + q log q). Para adiciones únicamente usaría DSU ordinario; para eliminaciones online o caminos más cortos elegiría una estructura dinámica más potente.
Errores comunes
- Revertir una unión para la eliminación → las fusiones no son invertibles → usar intervalos de vida útil y rollback.
- Usar compresión de caminos en DSU con rollback → muchas escrituras de padres no se registran → usar unión por tamaño sin compresión.
- Tratar la vida útil como cerrada
[add, remove]→ la arista permanece activa en la eliminación → usar[add, remove). - Refusionar cada arista en cada hoja → la complejidad pierde el beneficio del segment tree → fusionar en los nodos que cubren el intervalo.
- Restaurar solo un puntero a padre → las elecciones posteriores de unión por tamaño se corrompen → restaurar también el tamaño anterior.
- Prometer un método offline para actualizaciones online → los intervalos futuros son desconocidos → confirmar primero el modelo de interacción.
Preguntas de seguimiento y respuestas
¿Qué pasa si el mismo ID de relación se agrega nuevamente después de haber sido eliminado?
Crea un nuevo registro abierto para cada add y haz que remove cierre únicamente la vida útil actualmente abierta. El mismo ID producirá entonces múltiples intervalos disjuntos en lugar de sobrescribir el anterior.
¿Puede el mismo diseño responder el tamaño del componente actual?
Sí. Mantén size en la raíz, devuelve la raíz desde find y restaura los tamaños anteriores durante el rollback. Los agregados adicionales de componentes también necesitan valores anteriores en la pila de historial y actualizaciones reversibles.
¿Qué pasa si q es tan grande que la recursión o la memoria se convierten en el cuello de botella?
Verifica primero si el almacenamiento de intervalos O(q log q) entra en memoria. Luego reemplaza el DFS recursivo con una pila explícita, compacta el almacenamiento de aristas o procesa bloques de tiempo. No habilites la compresión de caminos, ya que rompería silenciosamente la corrección del rollback.
¿Por qué el método de la línea de tiempo no puede simplemente cambiarse a eliminación online?
El método necesita una marca de tiempo de eliminación para construir cada intervalo. La entrada online no revela esa marca de tiempo futura, por lo que el preprocesamiento no puede colocar la arista en el árbol. Utiliza una estructura diseñada para conectividad dinámica online y reevalúa su latencia y costo de implementación.