As arestas formam uma única árvore
A missão
Problema
Você recebe n nós rotulados de 0 a n - 1 e uma lista de arestas não direcionadas. Retorne se as arestas formam exatamente uma árvore: todo nó está conectado a todos os outros, e não há ciclo.
Exemplos
Input: n = 5, edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
Output: True
Input: n = 5, edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
Output: False
Por quê: 1, 2 e 3 formam um ciclo
Input: n = 4, edges = [[0, 1], [2, 3]]
Output: False
Por quê: edge case: não há ciclo, mas o grafo está em dois pedaços
Dicas
0 / 3
Uma árvore com n nós tem exatamente n - 1 arestas. Só essa contagem já descarta muitas entradas.
Com exatamente n - 1 arestas, um grafo é uma árvore exatamente quando não tem ciclo, porque um grafo acíclico com essa quantidade de arestas é automaticamente conexo.
Confira primeiro a contagem de arestas. Depois, una as duas pontas de cada aresta em um conjunto disjunto; se as duas pontas já compartilharem uma raiz, essa aresta fecha um ciclo, e a resposta é False.
- Tempo-alvo
- O(n · α(n))
- Espaço-alvo
- O(n)
Restrições
- nodes are labelled 0 to n − 1
Solução
Dois fatos sobre árvores fazem todo o trabalho. Uma árvore com n nós tem exatamente n - 1 arestas, e um grafo com n - 1 arestas e sem ciclo é sempre conexo, já que cada aresta que une dois componentes diferentes reduz a contagem de componentes em um, de n até exatamente 1. Então, depois da verificação da contagem, a única pergunta é se alguma aresta fecha um ciclo, e é exatamente isso que um conjunto disjunto (disjoint set) responde: uma aresta cujas duas pontas já têm a mesma raiz liga nós que já estavam conectados. O path halving mantém as árvores rasas. O tempo é O(n · α(n)), na prática linear, e o espaço é O(n).
def is_single_tree(n, edges):
if len(edges) != n - 1:
return False
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path halving
x = parent[x]
return x
for a, b in edges:
ra, rb = find(a), find(b)
if ra == rb: # already connected: this edge closes a cycle
return False
parent[ra] = rb
return True
print(is_single_tree(5, [[0, 1], [0, 2], [0, 3], [1, 4]])) # -> True
print(is_single_tree(5, [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]])) # -> False
print(is_single_tree(4, [[0, 1], [2, 3]])) # -> FalseTravou na ideia, e não no código? Componentes e ciclos explica isso.