难度: Medium
Submission
运行时间: 18 ms
内存: 17.2 MB
class UnionFind:
# 为了效率，我们不使用 makeset，而是
# 在构造函数同时产生所有集合
def __init__(self, n):
self.parent = [node for node in range(n)]
# 未进行任何优化的 find 方法。它会追踪到父连接
# 直到找到 A 的根节点，并返回那个根节点。
def find(self, A):
while A != self.parent[A]:
A = self.parent[A]
return A
# 未进行优化的 union 方法。
# 如果发生合并它返回 true，否则返回 false
def union(self, A, B):
# 找到 A 和 B 的根
root_A = self.find(A)
root_B = self.find(B)
# 检查 A 和 B 是否已经在同一个集合中
if root_A == root_B:
return False
# 合并包含 A 和 B 的集合
self.parent[root_A] = root_B
return True
class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
# 情况 1: 图必须包含 n - 1 条边。
if len(edges) != n - 1: return False
# 情况 2: 图必须包含单个连通分量
# 创建一个包含 n 个节点的新并查集对象。
unionFind = UnionFind(n)
# 添加每一条边。检查是否发生合并，
# 因为如果它没有，就一定有环
for A, B in edges:
if not unionFind.union(A, B):
return False
# 如果我们走到这一步，就没有环了！
return True
Explain
该题解使用了并查集来判断给定的边集是否构成一棵树。并查集是一种树形数据结构，用于处理不相交集合的合并及查询所属集合等操作。通过并查集，我们可以高效地判断图中是否存在环以及连通分量的个数。 具体思路如下： 1. 首先，树中边的数量必须等于节点数减一，否则一定不是树。 2. 接着，初始化一个大小为 n 的并查集，每个节点各自为一个集合。 3. 遍历所有的边，对于每条边 (A, B)，找到 A 和 B 所在集合的根节点。 - 如果 A 和 B 在同一个集合中，说明出现了环，不是树，返回 false。 - 如果 A 和 B 不在同一个集合中，则将它们所在的集合合并为一个集合。 4. 遍历完所有的边后，如果没有出现环，说明是一棵树，返回 true。
时间复杂度: O(n)
空间复杂度: O(n)
class UnionFind:
# 为了效率，我们不使用 makeset，而是
# 在构造函数同时产生所有集合
def __init__(self, n):
# 初始化父节点列表，每个节点的父节点初始为自己
self.parent = [node for node in range(n)]
# 未进行任何优化的 find 方法。它会追踪到父连接
# 直到找到 A 的根节点，并返回那个根节点。
def find(self, A):
while A != self.parent[A]:
A = self.parent[A]
return A
# 未进行优化的 union 方法。
# 如果发生合并它返回 true，否则返回 false
def union(self, A, B):
# 找到 A 和 B 的根节点
root_A = self.find(A)
root_B = self.find(B)
# 检查 A 和 B 是否已经在同一个集合中
if root_A == root_B:
return False
# 合并包含 A 和 B 的集合，将 A 的根节点的父节点设置为 B 的根节点
self.parent[root_A] = root_B
return True
class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
# 情况 1: 图必须包含 n - 1 条边。
if len(edges) != n - 1: return False
# 情况 2: 图必须包含单个连通分量
# 创建一个包含 n 个节点的新并查集对象。
unionFind = UnionFind(n)
# 添加每一条边。检查是否发生合并，
# 因为如果它没有，就一定有环
for A, B in edges:
if not unionFind.union(A, B):
return False
# 如果我们走到这一步，就没有环了！
return True
Explore
在本题的上下文中，选择未优化的 find 和 union 方法是因为问题规模通常较小，且操作的复杂度可以接受。使用未优化的方法简化了代码的实现，使得代码更易于理解和维护。尽管路径压缩或按秩合并可以显著提高并查集操作的效率，特别是在大规模数据或多次查询和合并操作的场景中，但在本题中，由于边的数量与节点数相近且操作次数有限，这些优化可能不会带来显著的性能提升。
在本题的上下文中，代码先检查边的数量是否等于节点数减一。如果条件满足，随后使用并查集检查是否存在环。此方法在处理连通图时是有效的，因为一个没有环的连通图正是一棵树。然而，如果图是非连通的，即使没有环，边的数量与节点数减一的条件也会导致算法返回 false。因此，这种方法只适用于连通图的情况，而题目假设或要求图应当是连通的（即一棵树）。
在判断一个结构是否为一棵树时，除了检查边的数量等于节点数减一这一必要条件外，还需要确保图是连通的且没有环。这两个条件可以通过并查集来验证：1) 使用并查集处理所有边，如果任何两个节点已经在同一集合中再次合并，表明存在环；2) 在处理完所有边后，如果所有节点都属于同一连通分量，则表明图是连通的。只有同时满足这些条件，结构才是一棵树。
这种做法主要是基于树的一个基本特性：在一个包含 n 个节点的树中，必然恰有 n-1 条边。这个条件是树的必要条件之一，但不是充分条件，因为单单边的数量等于节点数减一并不能保证没有环或图是连通的。因此，在这之后，解法还需要检查图是否连通且无环来确保结构真的是一棵树。如果边的数量不符，可以直接判断不是树，这种做法有效地排除了所有边数过多或过少的非树结构情况。