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

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

中くらい

のグラフがあります n ～のラベルが付いたノード 0 に n-1整数 n と次のリストが与えられます。 エッジ どこ エッジ[i] = [a _i , b _i ] ノード間に無向エッジがあることを示します _AI そして b_私 グラフで。

戻る 真実 指定されたグラフのエッジが有効なツリーを構成しているかどうか、および 間違い さもないと.

例 1:

入力： n = 5、エッジ = [[0,1],[0,2],[0,3],[1,4]]
出力： 真実

例 2:

入力： n = 5、エッジ = [[0,1],[1,2],[2,3],[1,3],[1,4]]
出力： 間違い

制約:

1 <= n <= 2000
0 <= エッジ.長さ <= 5000
エッジ[i].length == 2
0 <= a _i 、 b _i < n
a _i != b _i
自己ループや反復エッジはありません。

パイソン

				
					# 時間計算量: O(n) # 空間計算量: 入力による O(n) import リスト クラス UnionFind: def __init__(self, n: int) -> なし: self.parents = list(range(n)) def find( self, ノード: int) -> int: while ノード != self.parents[ノード]: ノード = self.parents[ノード] return ノード def Union(self, ノード X: int, ノード Y: int) -> ブール:parentX, parentY = self.find(nodeX), self.find(nodeY) ifparentX ==parentY: return False self.parents[parentX] =parentY return True class 解決策: def validTree(self, n: int,edges: List[List [int]]) -> bool: len(edges) != n - 1 の場合: False を返す disjointUnionSet = UnionFind(n) の startVertex、エッジの endVertex: disjointUnionSet.union(startVertex, endVertex) でない場合: False を返す true を返すn = 5 エッジ = [[0, 1], [0, 2], [0, 3], [2, 3]] print(Solution().validTree(n,edges))

中くらい

パイソン

関連記事