Pular para o conteúdo

Verificar se um par é alcançável

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

A missão

Problema

Uma rede tem n nós numerados de 0 a n menos 1 e uma lista de ligações de mão dupla entre pares de nós. Dados um nó de origem e um nó de destino, decida se alguma cadeia de ligações leva de um ao outro. Um nó sempre alcança a si mesmo.

Exemplos

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ê: as ligações formam dois grupos separados, {0, 1, 2} e {3, 4, 5}
Input:  n = 1, links = [], source = 0, target = 0
Output: True
Por quê: edge case: um nó alcança a si mesmo sem nenhuma ligação

Dicas

0 / 3

Tempo-alvo
O((n + m) · α(n))
Espaço-alvo
O(n)

Restrições

  • nodes are numbered 0 to n − 1

Travou na ideia, e não no código? O básico de conjuntos disjuntos explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado