El problema y cuándo se aplica
Asignar problemas a programadores es un modelo útil: los problemas están a la izquierda, los programadores a la derecha, y una arista significa que comparten una etiqueta requerida. Cada arista se puede seleccionar como máximo una vez, y el objetivo es maximizar las asignaciones. Una consigna de entrevista pública de PracHub modela esta asignación de elegibilidad como un emparejamiento bipartito y la extiende a la generación de aristas, coordinación distribuida y cambios en streaming; este artículo se centra en el núcleo de programación para una sola máquina.
Qué evalúa el entrevistador
- Distinguir entre cualquier emparejamiento factible, maximal y de cardinalidad máxima.
- Usar caminos de aumento para explicar por qué un emparejamiento puede crecer manteniendo las invariantes.
- Explicar la estratificación por capas con BFS y DFS para un conjunto de caminos de aumento más cortos disjuntos en vértices.
- Indicar el tiempo en el peor de los casos de O((V+E)√V), el almacenamiento O(V+E) y los límites del algoritmo.
Preguntas de aclaración previas
- ¿El objetivo es la cardinalidad máxima, o existen pesos, prioridades o restricciones de equidad?
- ¿Cuáles son los límites de n, m y E, y la entrada ya es bipartita y no contiene duplicados?
- ¿La respuesta debe devolver únicamente el tamaño, o cada par y cada vértice no emparejado?
- ¿El grafo es un lote estático, o se insertarán y eliminarán aristas bajo un objetivo de latencia en línea?
Una respuesta de 30 segundos
“Modelo las dos clases de objetos como los dos lados de un grafo bipartito y la elegibilidad como aristas. Mantengo pair_left y pair_right. Cada BFS comienza desde cada vértice izquierdo no emparejado y construye capas a través de aristas no emparejadas y emparejadas alternadas. Luego, DFS encuentra un conjunto de caminos de aumento más cortos disjuntos en vértices en ese grafo por capas; invertir cada camino incrementa el emparejamiento. Cuando no queda ningún camino de aumento, el teorema del camino de aumento garantiza un emparejamiento máximo. La complejidad en el peor de los casos es O((V+E)√V); para un grafo pequeño, una implementación de aumento más simple con DFS puede ser suficiente.”
Solución paso a paso
Paso 1: Construir el grafo y las invariantes
Almacena únicamente aristas factibles reales en listas de adyacencia. pair_left[u] y pair_right[v] deben apuntar entre sí, o ambos ser -1. Invertir un camino de aumento cambia únicamente sus aristas, por lo que ningún vértice recibe dos aristas emparejadas.
Paso 2: Construir capas con BFS
Comienza simultáneamente desde cada vértice izquierdo no emparejado. Recorre una arista no emparejada hacia el lado derecho y luego la arista emparejada de regreso a un vértice izquierdo, registrando la capa más corta. Conserva las capas más cortas que puedan alcanzar un vértice derecho no emparejado para que DFS no explore caminos más largos en la misma fase.
Paso 3: Aumentar en lotes con DFS
Ejecuta DFS desde cada vértice izquierdo no emparejado. Llegar a un vértice derecho no emparejado tiene éxito. Llegar a un vértice derecho emparejado recurre a través de su vértice izquierdo emparejado solo cuando la capa se incrementa en uno. Un cursor de adyacencia por vértice izquierdo evita reexaminar aristas fallidas en la misma fase.
Paso 4: Corrección y terminación
Un camino de aumento tiene una arista no emparejada más que aristas emparejadas, por lo que la diferencia simétrica a lo largo de él aumenta la cardinalidad en uno. El teorema del camino de aumento establece que un emparejamiento es máximo exactamente cuando no existe ningún camino de aumento. Cada fase incrementa el emparejamiento, por lo que el bucle termina.
Paso 5: Complejidad y compensaciones
Hopcroft–Karp tiene un tiempo en el peor de los casos de O((V+E)√V), espacio auxiliar de O(V) y almacenamiento de grafo de O(V+E). La implementación de referencia de Princeton también deriva una cobertura mínima de vértices; esta consigna solo requiere un emparejamiento. Para un grafo pequeño, el DFS por vértice izquierdo es más corto pero puede tomar O(VE) en el peor de los casos. Los objetivos ponderados requieren el algoritmo húngaro o flujo de costo mínimo en su lugar.
Implementación ejecutable en Python
from collections import deque
def hopcroft_karp(left_size, right_size, edges):
adj = [[] for _ in range(left_size)]
for left, right in edges:
adj[left].append(right)
pair_left = [-1] * left_size
pair_right = [-1] * right_size
distance = [-1] * left_size
def bfs():
queue = deque()
for left in range(left_size):
if pair_left[left] == -1:
distance[left] = 0
queue.append(left)
else:
distance[left] = -1
found = False
while queue:
left = queue.popleft()
for right in adj[left]:
mate = pair_right[right]
if mate == -1:
found = True
elif distance[mate] == -1:
distance[mate] = distance[left] + 1
queue.append(mate)
return found
def dfs(left, next_edge):
while next_edge[left] < len(adj[left]):
right = adj[left][next_edge[left]]
next_edge[left] += 1
mate = pair_right[right]
if mate == -1 or (
distance[mate] == distance[left] + 1
and dfs(mate, next_edge)
):
pair_left[left] = right
pair_right[right] = left
return True
distance[left] = -1
return False
matching = 0
while bfs():
next_edge = [0] * left_size
for left in range(left_size):
if pair_left[left] == -1 and dfs(left, next_edge):
matching += 1
return matching, pair_leftUn ejemplo de respuesta de alta calidad
“Primero confirmo que el objetivo es la cardinalidad máxima, no un emparejamiento ponderado, y modelo la elegibilidad como aristas bipartitas. Dos arreglos de pares mantienen una invariante bidireccional. BFS organiza en capas los caminos de aumento más cortos desde todos los vértices izquierdos no emparejados; DFS utiliza cursores de aristas actuales para encontrar tantos caminos disjuntos en vértices en ese grafo por capas como sea posible, y luego invierte sus aristas. Cuando no queda ningún camino, el teorema del camino de aumento demuestra la optimalidad. La implementación utiliza O((V+E)√V) de tiempo y O(V+E) de almacenamiento; los grafos pequeños pueden usar DFS simple, mientras que los objetivos ponderados necesitan el método húngaro o flujo de costo mínimo.”
Errores comunes
- Llamar máximo a un resultado voraz; un emparejamiento maximal puede ser mucho más pequeño que uno máximo.
- Almacenar solo un lado de cada par y crear una ocupación duplicada después de una inversión.
- Detener BFS en cualquier camino alcanzable, lo cual rompe la agrupación por capas más cortas.
- Omitir los cursores de aristas actuales y reexaminar aristas fallidas dentro de una misma fase.
- Afirmar O((V+E)√V) para emparejamientos generales, ponderados o actualizados dinámicamente.
Preguntas de seguimiento y respuestas sólidas
¿Cómo se generan las aristas de elegibilidad sin comparar todos los pares n×m?
Construye un índice invertido por etiqueta. Agrupa en buckets los objetos del lado derecho, luego une y desduplica los buckets para cada objeto izquierdo. E aún puede ser grande, así que reporta E, el sesgo de etiquetas populares (hot-tags) y los límites de memoria.
¿Por qué el algoritmo puede detenerse cuando no hay ningún camino de aumento?
Cada camino de aumento incrementa el tamaño del emparejamiento en uno. El teorema del camino de aumento establece que existe un emparejamiento más grande exactamente cuando existe un camino de aumento, por lo que no encontrar ninguno demuestra la cardinalidad máxima.
¿Qué cambia para las preferencias ponderadas?
Hopcroft–Karp optimiza únicamente la cantidad de aristas. Usa el algoritmo húngaro o flujo máximo de costo mínimo, y redefine la complejidad, los límites de pesos enteros y el plan de contingencia cuando no existe una asignación factible.
¿Cómo manejarías la constante rotación de aristas?
El algoritmo por lotes es adecuado para el recálculo. Un servicio en línea puede buscar localmente caminos de aumento alrededor de los vértices afectados, pero debe definir la latencia, los límites de reasignación y el acuerdo sobre la no optimalidad temporal.