Las aristas forman un solo árbol
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
Un árbol con n nodos tiene exactamente n - 1 aristas. Ese conteo por sí solo descarta muchas entradas.
Con exactamente n - 1 aristas, un grafo es un árbol precisamente cuando no tiene ciclos, porque un grafo acíclico con esa cantidad de aristas está conectado automáticamente.
Revisa primero el conteo de aristas. Luego une los dos extremos de cada arista en una estructura de conjuntos disjuntos, y si ambos extremos ya comparten raíz, esa arista cierra un ciclo, así que la respuesta es False.
- Tiempo objetivo
- O(n · α(n))
- Espacio objetivo
- O(n)
Restricciones
- nodes are labelled 0 to n − 1
Solución
Dos hechos sobre los árboles hacen todo el trabajo. Un árbol con n nodos tiene exactamente n - 1 aristas, y un grafo con n - 1 aristas y sin ciclos siempre está conectado, ya que cada arista que une dos componentes distintos reduce en uno la cantidad de componentes, de n hasta exactamente 1. Así que, después de revisar el conteo, la única pregunta es si alguna arista cierra un ciclo, y eso es justo lo que responde una estructura de conjuntos disjuntos: una arista cuyos dos extremos ya tienen la misma raíz conecta nodos que ya estaban conectados. El path halving (reducir el camino a la mitad) mantiene los árboles poco profundos. El tiempo es O(n · α(n)), en la práctica lineal, y el espacio es 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]])) # -> False¿Lo que te frena es la idea y no el código? Componentes y ciclos lo explica.