Saltar al contenido

Comprobar si un par es alcanzable

Fácil#union-find#connectivity~15 min

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

Tiempo objetivo
O((n + m) · α(n))
Espacio objetivo
O(n)

Restricciones

  • nodes are numbered 0 to n − 1

¿Lo que te frena es la idea y no el código? Fundamentos de conjuntos disjuntos lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio