[Leetcode] 0261. Gráfico de árbol válido

Explore diversas soluciones LeetCode en Python, C++, JavaScript, SQL y TypeScript. Ideal para preparación de entrevistas, aprendizaje y práctica de código en múltiples lenguajes de programación. Enlace de repositorio de Github

Tabla de contenido

Medio

Tienes una gráfica de norte nodos etiquetados desde 0 a n-1Se le proporciona un número entero n y una lista de bordes dónde bordes [i] = [a _i , b _i ] indica que hay un borde no dirigido entre nodos _AI y b _yo en el gráfico.

Devolver verdadero si los bordes del gráfico dado forman un árbol válido, y FALSO de lo contrario.

Ejemplo 1:

Aporte: n = 5, aristas = [[0,1],[0,2],[0,3],[1,4]]
Producción: verdadero

Ejemplo 2:

Aporte: n = 5, aristas = [[0,1],[1,2],[2,3],[1,3],[1,4]]
Producción: FALSO

Restricciones:

1 <= norte <= 2000
0 <= bordes.longitud <= 5000
bordes[i].longitud == 2
0 <= a _yo , b _yo < norte
a _i ! = b _i
No hay bucles automáticos ni bordes repetidos.

Pitón

				
					Complejidad de tiempo de #: O(n) Complejidad de espacio de #: O(n) al escribir import List clase UnionFind: def __init__(self, n: int) -> Ninguno: self.parents = list(range(n)) def find( self, nodo: int) -> int: while nodo! = self.parents[nodo]: nodo = self.parents[nodo] return node def union(self, nodeX: int, nodeY: int) -> bool: parentX, parentY = self.find(nodeX), self.find(nodeY) if parentX == parentY: return False self.parents[parentX] = parentY return True class Solución: def validTree(self, n: int, bordes: Lista[Lista [int]]) -> bool: si len(bordes) != n - 1: devuelve False disjointUnionSet = UnionFind(n) para startVertex, endVertex en bordes: si no disjointUnionSet.union(startVertex, endVertex): devuelve False devuelve True n = 5 aristas = [[0, 1], [0, 2], [0, 3], [2, 3]] print(Solution().validTree(n, aristas))

Medio

Pitón

Artículos relacionados