本文详解 leetcode 547 题中 union-find 实现的典型错误，包括未执行 find 查找根节点、错误合并非根节点、秩（rank）误增等问题，并提供完整可运行的修正代码与关键原理说明。
本文详解 leetcode 547 题中 union-find 实现的典型错误，包括未执行 find 查找根节点、错误合并非根节点、秩（rank）误增等问题，并提供完整可运行的修正代码与关键原理说明。
在解决「省份数量」（LeetCode 547）这类连通分量问题时，Union-Find（并查集）是高效且常用的数据结构。但初学者常因忽略其核心契约而引入隐蔽 Bug——例如直接使用 parent[i] 和 parent[j] 比较或赋值，却未先通过 find 定位真正的根节点。这会导致逻辑断裂：两个节点虽属同一连通分量，却因路径未压缩、父指针未回溯而被误判为不同集合，最终使 count 计数偏小（如题中输出 2 而非正确答案 3）。
? 核心错误剖析
原代码存在三个关键缺陷：
- 缺失 find 操作：p1, p2 = parent[i], parent[j] 仅取直接父节点，而非集合根节点。若 i → a → root，j → b → root，则 parent[i] ≠ parent[j] 仍成立，但二者实属同一集合。
- 错误的 union 目标：parent[j] = p1 或 parent[i] = p2 修改的是子节点的父指针，而非根节点之间的连接。正确做法是 parent[p1] = p2（将一棵树的根挂到另一棵树的根下）。
- 秩（rank）更新逻辑错误：rank 表示以该节点为根的树的高度（或近似高度）。仅当两树 rank 相等时，合并后新根的 rank 才需 +1；否则，新树高度不变，不应无条件 += 1。
✅ 正确实现：路径压缩 + 按秩合并
以下为修复后的完整实现，采用路径折半（path halving）优化 find（兼顾简洁性与性能），并在 union 中严格操作根节点、精准更新 rank：
class Solution(object):
def findCircleNum(self, isConnected):
def find(i):
# 路径折半：每次跳两级，加速收敛
while i != parent[i]:
parent[i] = parent[parent[i]] # 压缩当前节点的父节点
i = parent[i]
return i
n = len(isConnected)
parent = list(range(n)) # 初始化：每个节点自成一集
rank = [1] * n # rank[i] 表示以 i 为根的树的高度
count = n # 初始有 n 个独立集合（省）
for i in range(n):
for j in range(i + 1, n):
if isConnected[i][j] == 1:
root_i, root_j = find(i), find(j)
if root_i != root_j:
count -= 1 # 合并两个集合，总数减一
# 按秩合并：小树挂到大树下
if rank[root_i] > rank[root_j]:
parent[root_j] = root_i
elif rank[root_i] < rank[root_j]:
parent[root_i] = root_j
else: # rank 相等，任选其一为根，且该根 rank +1
parent[root_j] = root_i
rank[root_i] += 1
return count⚠️ 关键注意事项
- find 是一切的前提：任何比较（root_i != root_j）或合并（parent[root_j] = root_i）前，必须调用 find 获取真实根节点。切勿跳过。
- union 操作对象只能是根节点：parent[x] = y 中的 x 和 y 必须是各自集合的根（即满足 find(x) == x 和 find(y) == y）。
- rank 不代表当前节点深度，而是树高上界：它仅用于指导合并方向，且只在两树高度相等时递增。误增会导致后续合并偏向错误方向，降低效率甚至引入逻辑错误。
- 路径压缩与按秩合并可共存：本例的路径折半（parent[i] = parent[parent[i]]）与按秩合并互不冲突，共同保障接近常数级的均摊时间复杂度（≈ O(α(n))）。
✅ 验证结果
对题目提供的 15×15 测试矩阵运行上述代码，返回 3，与期望一致。该解法时间复杂度为 O(n² α(n))，空间复杂度 O(n)，稳健适用于大规模稠密图场景。
掌握 find 的必要性、union 的目标对象以及 rank 的语义，是写出正确 Union-Find 的铁三角。每一次跳过 find，都是在为难以复现的连通性错误埋下伏笔。
