Contar componentes conexas mientras las aristas llegan de forma dinámica. ¿Cuál es la mejor estructura?
Opciones
- Union-Find con compresión de caminos y rangos (Opción correcta)
- Una pila que guarda los vértices de cada grupo
- Un árbol binario de búsqueda con todos los vértices vistos
- Un Bloom filter que guarda las aristas hasta ahora
Respuesta
Union-Find (disjoint set) con compresión de caminos y unión por rango
Por qué
Union-Find mantiene grupos de elementos. find(x) devuelve el líder del grupo; union(a, b) fusiona dos grupos.
Cuando llega una arista a-b, únelos; el número de componentes baja en uno si estaban en grupos distintos.
Con compresión de caminos y unión por rango, cada operación es casi O(1). También se usa en el árbol de expansión mínima de Kruskal.
Recuerda
'¿Están conectados?' de forma dinámica → Union-Find.