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

/ Leetcode, artículo técnico / Por

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))

Artículos relacionados