带路径压缩的联合查找- Python算法

Question

处理以下问题(https://leetcode.com/problems/friend-circles/):

一个班有N个学生。他们有些是朋友，有些不是。他们的友谊本质上是可传递的。比如A是B的直接好友，B是C的直接好友，那么A就是C的间接好友，而我们定义的朋友圈就是一群直接或者间接好友的同学。

给定一个N*N矩阵M，表示班级学生之间的朋友关系。如果M[i][j]=1，则第i和第j个学生是彼此的直接朋友，否则不是。你必须输出所有学生之间的朋友圈总数。例如：

Input: 
[[1,1,0],
 [1,1,0],
 [0,0,1]]
Output: 2
Explanation:The 0th and 1st students are direct friends, so they are in a friend circle. 
The 2nd student himself is in a friend circle. So return 2.


Input: 
[[1,1,0],
 [1,1,1],
 [0,1,1]]
Output: 1
Explanation:The 0th and 1st students are direct friends, the 1st and 2nd students are direct friends, 
so the 0th and 2nd students are indirect friends. All of them are in the same friend circle, so return 1.

这是我的解决方案：

class Solution(object):
    def findCircleNum(self, M):
        """
        :type M: List[List[int]]
        :rtype: int
        """
        parents = [i for i in range(len(M))]
        count = len(M)

        def union(i, j):
            parent_i = get_parent(i)
            parent_j = get_parent(j)

            parents[i] = parent_j

        def get_parent(i):
            while not parents[i] == i:
                parents[i] = parents[parents[i]] # compress
                i = parents[i]
            return i

        for i in range(len(M)):
            for j in range(i+1, len(M)):
                if M[i][j] == 1:
                    union(i, j)

        return sum(i == parent for i, parent in enumerate(parents))

此代码中断以下输入：

[
[1,0,0,0,0,0,0,0,0,1,0,0,0,0,0],
[0,1,0,1,0,0,0,0,0,0,0,0,0,1,0],
[0,0,1,0,0,0,0,0,0,0,0,0,0,0,0],
[0,1,0,1,0,0,0,1,0,0,0,1,0,0,0],
[0,0,0,0,1,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,1,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,1,0,0,0,0,0,0,0,0],
[0,0,0,1,0,0,0,1,1,0,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0,0,0],
[1,0,0,0,0,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0,0,0],
[0,0,0,1,0,0,0,0,0,0,0,1,0,0,0],
[0,0,0,0,1,0,0,0,0,0,0,0,1,0,0],
[0,1,0,0,0,0,0,0,0,0,0,0,0,1,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]
]

（我的解决方案返回 10 而不是 8），我在跟踪算法不正确的位置时遇到了一些麻烦。有人在这里看到什么问题吗？注意：它被包装在一个类解决方案中，因为这是一个Leetcode的东西。

Answer 1

您编写了父母[i]=parent_j而不是父母[parent_i]=parent_j，允许将对象i移动到集合中的可能性parent_j而不会带来其集合的其余部分。