Pular para o conteúdo

As arestas formam uma única árvore

Fácil#union-find#cycle-detection~15 min

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

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

Restrições

  • nodes are labelled 0 to n − 1

Travou na ideia, e não no código? Componentes e ciclos explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado