企业官网建设流程全解析

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 条边，且无环。