Объединение Найти с путевым сжатием - алгоритм Python - PullRequest
Новая
       43

Объединение Найти с путевым сжатием - алгоритм Python

0 голосов
/ 16 октября 2018

Работа над следующей проблемой (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), и у меня возникла небольшая проблема с отслеживанием неправильного алгоритма. Кто-нибудь видит здесь что-то не так? NB: оно заключено в решение класса так какэто вещь Leetcode.

1 Ответ

0 голосов
/ 18 октября 2018

Вы написали parents[i] = parent_j вместо parents[parent_i] = parent_j, что позволяет перемещать объект i в набор parent_j без переноса остальной части его набора.

...