[Leetcode] 0261. Graph Valid Tree

/ Leetcode, Technical Article / By

Explore diverse LeetCode solutions in Python, C++, JavaScript, SQL, and TypeScript. Ideal for interview prep, learning, and code practice in multiple programming languages. Github Repo Link

Table of contents

Medium

You have a graph of n nodes labeled from 0 to n-1. You are given an integer n and a list of edges where edges[i] = [a i , b i ] indicates that there is an undirected edge between nodes artificial intelligence and b i in the graph.

Return true if the edges of the given graph make up a valid tree, and false otherwise.

 

Example 1:

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true

Example 2:

Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
Output: false

 

Constraints:

  • 1 <= n <= 2000
  • 0 <= edges.length <= 5000
  • edges[i].length == 2
  • 0 <= a i , b i < n
  • a i != b i
  • There are no self-loops or repeated edges.

Python

				
					# time complexity: O(n) # space complexity: O(n) from typing import List class UnionFind: def __init__(self, n: int) -> None: self.parents = list(range(n)) def find( self, node: int) -> int: while node != self.parents[node]: node = self.parents[node] 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 Solution: def validTree(self, n: int, edges: List[List [int]]) -> bool: if len(edges) != n - 1: return False disjointUnionSet = UnionFind(n) for startVertex, endVertex in edges: if not disjointUnionSet.union(startVertex, endVertex): return False return True n = 5 edges = [[0, 1], [0, 2], [0, 3], [2, 3]] print(Solution().validTree(n, edges))

related articles