排查LeetCode 547省份数量问题的Union-Find实现错误

你的并查集实现存在两个核心问题，导致结果错误：

1. 未使用带路径压缩的find函数 #

你直接使用parent[i]和parent[j]获取的是节点的直接父节点，而非所在集合的根节点。当节点已经被合并到其他集合中时，直接父节点可能不是最终的根，这会导致错误地判断两个节点属于不同集合，进而重复减少省份计数。

2. 秩（rank）的更新逻辑错误 #

你每次合并时都直接将父节点的秩加1，正确的做法应该是只有当合并两个秩相同的树时，才将根节点的秩加1，否则保持秩不变，这样才能保证树的平衡。

修复后的代码 #

class Solution(object):
    def findCircleNum(self, m):
        n = len(m)
        parent = [i for i in range(n)]
        rank = [1 for i in range(n)]
        count = n
        
        # 带路径压缩的find函数
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])  # 路径压缩，直接指向根节点
            return parent[x]
        
        for i in range(n):
            for j in range(i+1, n):
                if m[i][j] == 1:
                    root_i = find(i)
                    root_j = 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:
                            parent[root_j] = root_i
                            rank[root_i] += 1
        return count

关键修复点说明 #

• 路径压缩的find函数：确保每次查找后，节点直接指向根节点，后续查找效率更高，同时保证获取的是真正的集合根节点。
• 按秩合并：根据树的高度（秩）决定合并方向，避免树退化为链表，同时仅在合并两个同高度树时更新秩，维持树的平衡。

用修复后的代码运行你的测试用例，会返回正确结果3。

内容的提问来源于stack exchange，提问作者Akanksha