Verificar se um par é alcançável
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
A rota exata não importa, só se os dois nós acabam no mesmo grupo conectado.
Comece com cada nó em um grupo próprio. Cada ligação diz que dois grupos são, na verdade, um só.
Dê a cada nó um ponteiro para o pai que aponta para ele mesmo. Para cada ligação, encontre a raiz das duas pontas seguindo os ponteiros para o pai e aponte uma raiz para a outra. No fim, a resposta é se a origem e o destino têm a mesma raiz.
- Tempo-alvo
- O((n + m) · α(n))
- Espaço-alvo
- O(n)
Restrições
- nodes are numbered 0 to n − 1
Solução
Cada ligação junta os grupos das suas duas pontas; então, depois de processar todas as ligações, os conjuntos disjuntos (disjoint set) são exatamente os grupos conectados, seja qual for a ordem em que as ligações chegaram. O alcance passa a ser uma única comparação de raízes. O path halving, que aponta cada nó visitado para o avô durante um find, mantém as cadeias de pais curtas sem nenhum controle extra. Com m ligações, o tempo é O((n + m) vezes a função inversa de Ackermann), na prática linear, e o espaço é 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)) # -> TrueTravou na ideia, e não no código? O básico de conjuntos disjuntos explica isso.