[リートコード] 0261. グラフ有効ツリー

Python、C++、JavaScript、SQL、TypeScript の多様な LeetCode ソリューションを探索してください。面接の準備、学習、複数のプログラミング言語でのコードの練習に最適です。 Github リポジトリリンク

中くらい

You have a graph of n nodes labeled from 0 に n-1. You are given an integer n and a list of edges どこ edges[i] = [a_i, b_i] indicates that there is an undirected edge between nodes _AI そして b_私 in the graph.

戻る 真実 if the edges of the given graph make up a valid tree, and 間違い otherwise.

例 1:

入力： n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
出力： 真実

例 2:

入力： n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
出力： 間違い

制約:

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.

パイソン

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

中くらい

パイソン

関連記事