本文详解 leetcode 547 题中 union-find 算法实现的典型缺陷，包括未执行路径压缩导致的根节点误判、非根节点直接参与合并引发的结构断裂，以及秩更新逻辑错误，并提供修复后的完整可运行代码。
本文详解 leetcode 547 题中 union-find 算法实现的典型缺陷，包括未执行路径压缩导致的根节点误判、非根节点直接参与合并引发的结构断裂，以及秩更新逻辑错误，并提供修复后的完整可运行代码。
在使用并查集（Union-Find）求解连通分量类问题（如 LeetCode 547. Number of Provinces）时，看似简洁的代码常因忽略核心机制而返回错误结果。题中测试用例返回 2 而非预期 3，正是典型实现漏洞的外在表现。根本原因在于：原始代码跳过了关键的 find 操作，直接使用 parent[i] 和 parent[j] 判断连通性，这仅反映“一层父节点”，而非真正的集合代表元（即根节点）。
核心问题剖析
缺失 find 操作 → 根节点误判
并查集的 union 前必须先 find 各节点的根。若仅比较 parent[i] != parent[j]，当 i→a→root、j→b→root（即二者同属一棵树但父节点不同）时，会错误触发合并或计数减一，破坏连通性语义。非根节点参与合并 → 树结构断裂
原代码中 parent[j] = p1 或 parent[i] = p2 是危险操作：i/j 很可能不是其所在树的根，将其父指针重定向会导致子树与原根脱节，后续 find 无法收敛到统一根节点。秩（rank）更新逻辑错误
rank 表示以该节点为根的树的高度（或近似深度）。仅当两棵树高度相等时，合并后新根的 rank 才需 +1；若 r1 > r2，将矮树挂到高树下，rank[p1] 不应变化。原代码无条件 += 1 会导致秩失真，削弱按秩合并的优化效果。
正确实现：路径压缩 + 按秩合并
以下为修复后的完整实现，采用路径折半（path halving） 进行压缩（兼顾简洁与效率），并严格遵循“先 find，再 union 根，最后按需更新 rank”原则：
class Solution(object):
def findCircleNum(self, isConnected):
def find(x):
# 路径折半：每次迭代将 x 的父节点设为其祖父节点，加速扁平化
while x != parent[x]:
parent[x] = parent[parent[x]]
x = parent[x]
return x
n = len(isConnected)
parent = list(range(n)) # 初始化：每个节点自成一族
rank = [1] * n # 初始秩均为 1（单节点树高度为 1）
provinces = 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:
provinces -= 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: # 秩相等，任选其一为根，且该根秩 +1
parent[root_j] = root_i
rank[root_i] += 1
return provinces关键注意事项
- ✅ find 必须被调用：所有涉及连通性判断或合并操作前，务必通过 find(x) 获取真实根节点。
- ✅ union 操作对象只能是根节点：parent[root_a] = root_b，而非 parent[a] = root_b。
- ✅ rank 更新需谨慎：仅当 rank[root_a] == rank[root_b] 时，新根的 rank 才 +1；否则保持不变。
- ⚠️ 避免冗余操作：union 逻辑（含 rank 更新）应严格置于 if root_i != root_j: 分支内，防止无效计算。
- ? 调试建议：在 find 中添加日志（如 print(f"find({x}) -> {x}")）或使用可视化工具观察 parent 数组演化过程，可快速定位路径压缩失效点。
该实现已通过题中全部测试用例，时间复杂度接近 $O(n^2 \alpha(n))$（$\alpha$ 为反阿克曼函数，实际视为常数），空间复杂度 $O(n)$，兼具正确性、效率与可维护性。掌握这些底层细节，是写出健壮并查集代码的关键。
