Skip to main content
 首页 » 编程设计

python之Union Find with Path Compression之Python 算法

2024年12月31日9落叶

正在解决以下问题(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] 
] 

(我的解决方案返回 10 而不是 8)并且我在跟踪我的算法不正确的地方时遇到了一些麻烦。有人在这里看到什么不对吗?注意:它包含在 类解决方案 中,因为这是 Leetcode 的东西。

请您参考如下方法:

你写的是 parents[i] = parent_j 而不是 parents[parent_i] = parent_j,允许将对象 i 移动到设置 parent_j 而不带它的其余部分。