Saltar al contenido

Las aristas forman un solo árbol

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

La misión

Problema

Recibes n nodos etiquetados de 0 a n - 1 y una lista de aristas no dirigidas. Devuelve si las aristas forman exactamente un árbol: cada nodo está conectado con todos los demás y no hay ningún ciclo.

Ejemplos

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 y 3 forman un ciclo
Input:  n = 4, edges = [[0, 1], [2, 3]]
Output: False
Por qué: caso límite: no hay ciclo, pero el grafo está en dos partes

Pistas

0 / 3

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

Restricciones

  • nodes are labelled 0 to n − 1

¿Lo que te frena es la idea y no el código? Componentes y ciclos lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio