Comprobar si un par es alcanzable
La misión
Problema
Una red tiene n nodos numerados de 0 a n menos 1 y una lista de conexiones bidireccionales entre pares de nodos. Dados un nodo de origen y un nodo de destino, decide si alguna cadena de conexiones lleva de uno al otro. Un nodo siempre se alcanza a sí mismo.
Ejemplos
Input: n = 3, links = [[0, 1], [1, 2], [2, 0]], source = 0, target = 2
Output: True
Input: n = 6, links = [[0, 1], [0, 2], [3, 5], [5, 4], [4, 3]], source = 0, target = 5
Output: False
Por qué: las conexiones forman dos grupos separados, {0, 1, 2} y {3, 4, 5}
Input: n = 1, links = [], source = 0, target = 0
Output: True
Por qué: caso límite: un nodo se alcanza a sí mismo sin ninguna conexión
Pistas
0 / 3
El camino exacto no importa, solo si los dos nodos terminan en el mismo grupo conectado.
Empieza con cada nodo en un grupo propio. Cada conexión te dice que dos grupos en realidad son uno.
Dale a cada nodo un puntero al padre que apunte a sí mismo. Para cada conexión, encuentra la raíz de ambos extremos siguiendo los punteros al padre y apunta una raíz a la otra. Al final, la respuesta es si el origen y el destino tienen la misma raíz.
- Tiempo objetivo
- O((n + m) · α(n))
- Espacio objetivo
- O(n)
Restricciones
- nodes are numbered 0 to n − 1
Solución
Cada conexión fusiona los grupos de sus dos extremos, así que después de procesar todas las conexiones los conjuntos disjuntos son exactamente los grupos conectados, sin importar el orden en que llegaron las conexiones. La alcanzabilidad es entonces una sola comparación de raíces. El path halving (reducir el camino a la mitad), que apunta cada nodo visitado a su abuelo durante un find, mantiene cortas las cadenas de padres sin ninguna contabilidad extra. Con m conexiones, el tiempo es O((n + m) por la inversa de Ackermann), en la práctica lineal, y el espacio es O(n).
def reachable(n, links, source, target):
parent = list(range(n)) # every node starts alone
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path halving
x = parent[x]
return x
for u, v in links:
parent[find(u)] = find(v) # a link merges two groups
return find(source) == find(target)
print(reachable(3, [[0, 1], [1, 2], [2, 0]], 0, 2)) # -> True
print(reachable(6, [[0, 1], [0, 2], [3, 5], [5, 4], [4, 3]], 0, 5)) # -> False
print(reachable(1, [], 0, 0)) # -> True¿Lo que te frena es la idea y no el código? Fundamentos de conjuntos disjuntos lo explica.