Union Find with Path Compression - Python 算法

Question

正在解决以下问题 (https://leetcode.com/problems/friend-circles/)：

There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if A is a direct friend of B, and B is a direct friend of C, then A is an indirect friend of C. And we defined a friend circle is a group of students who are direct or indirect friends.

Given a N*N matrix M representing the friend relationship between students in the class. If M[i][j] = 1, then the ith and jth students are direct friends with each other, otherwise not. And you have to output the total number of friend circles among all the students. Ex:

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]
]

（我的解决方案 returns 10 而不是 8）而且我在追踪我的算法不正确的地方时遇到了一些麻烦。有人在这里看到什么不对吗？注意：它包含在 class 解决方案中 因为这是 Leetcode 的东西。

Answer 1

您写了 parents[i] = parent_j 而不是 parents[parent_i] = parent_j，允许将对象 i 移动到集合 parent_j 中而无需将其其余部分带入集合中。

Union Find with Path Compression - Python 算法

Union Find with Path Compression - Python algorithm

python

union-find

connected-components