LeetCode省份数量题并查集（路径压缩+按秩合并）未过边缘用例求助

• 直接读取root数组统计根节点的方式错误。路径压缩是在find方法执行时才会更新节点的根指向，未主动调用find的节点在root数组中存储的仍然是历史父节点，而非最终的根节点，因此去重统计时会把非根节点误认为是独立根，导致计数偏大。

修改Solution类中findCircleNum的返回逻辑，遍历所有节点主动调用find获取真实根后再去重统计：

class Solution:
    def findCircleNum(self, M) -> int:
        edges = []
        side = len(M)
        for row in range(side):
            for col in range(side):
                if M[row][col] == 1:
                    edges.append((row, col))

        finder = UnionFind(side)
        for x, y in edges:
            finder.union(x, y)

        # 改动点：每个节点主动调用find获取真实根后去重
        return len(set(finder.find(i) for i in range(side)))

省份数量问题的邻接矩阵是对称的，当前全量遍历会把每条边重复添加两次（比如(i,j)和(j,i)），可以只遍历上三角区域减少无效union操作，不影响正确性：

for row in range(side):
    # 只遍历col >= row的部分
    for col in range(row, side):
        if M[row][col] == 1:
            edges.append((row, col))

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