LeetCode 261：以图判树 | 并查集

LeetCode 261以图判树 | 并查集引言以图判树Graph Valid Tree是 LeetCode 第 261 题难度为 Medium。题目要求判断给定的边是否能构成一棵树。算法实现def validTree(n, edges): if len(edges) ! n - 1: return False parent list(range(n)) def find(x): while parent[x] ! x: parent[x] parent[parent[x]] x parent[x] return x def union(x, y): px, py find(x), find(y) if px py: return False parent[px] py return True for u, v in edges: if not union(u, v): return False return True复杂度分析时间复杂度O(V E)空间复杂度O(V)总结树的特点V 个节点恰好有 V-1 条边且无环。