[Leetcode] 0261. Graph Valid Tree

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

內容目錄

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

Medium

Python

相關文章