-1

我尝试对这个问题使用 Union find 方法，但没有通过这个案例，有人可以让我了解为什么会这样吗？

find() : 对于 find 方法有路径压缩 union() : 对于 union 有按等级联合

问题链接

到目前为止通过 108/113 例 返回 5 预期 4

"""
[[1,1,0,0,0,0,0,1,0,1],
 [1,1,0,0,0,0,0,0,0,0],
 [0,0,1,0,0,0,1,0,0,0],
 [0,0,0,1,0,0,0,0,0,0],
 [0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,1,0,0,0,0],
 [0,0,1,0,0,0,1,1,0,0],
 [1,0,0,0,0,0,1,1,0,0],
 [0,0,0,0,0,0,0,0,1,1],
 [1,0,0,0,0,0,0,0,1,1]]
"""
class UnionFind:
    # How many cities there are going to be
    def __init__(self, size):
        self.root = [i for i in range(size)]
        # rank used to help when union 2 trees
        # join the shorter into the higher tree
        # our tree does not increase height if possible
        self.rank = [1] * size

    def find(self, x):
        """Return the root of the vertex"""
        if x == self.root[x]:
            # We have reached the root node which
            # has root equal itself
            return x
        parent = self.root[x]
        # We recursively look up the branch
        # to search for parent of parent till root
        self.root[x] = self.find(parent)
        return self.root[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        # Now we compare to see which tree "rank higher"
        # aka taller and we will add shorter tree to it
        if self.rank[rootX] > self.rank[rootY]:
            self.root[rootY] = rootX
        elif self.rank[rootX] < self.rank[rootY]:
            self.root[rootX] = rootY
        else:
            # When both tree have same height
            # When choose either and increase
            # the rank for that root
            self.root[rootY] = rootX
            self.rank[rootX] += 1

    def is_connected(self, x, y):
        """Return whether 2 vertex has the same root aka connected"""
        return self.find(x) == self.find(y)


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)

        return len(set([root for root in finder.root]))
4

2 回答 2

0

啊哈！找到了答案

它返回比实际具有更多不同根的原因是因为这些顶点的根尚未更新

我要做的就是在最后添加一个循环来对每个顶点执行 find() 操作，以更新其所有父节点的根值

find() 操作会递归遍历到根节点，在返回的路上会更新途中所有节点的根值

for vertex in range(side):
    uf.find(vertex)

谢谢你们！

于 2021-08-30T02:08:05.363 回答
0

尽管find在联合查找树中的每个节点上启动都可以解决问题，但只计算实际根的数量会更有效，即那些通过root属性具有自引用的节点：

return sum(1 for x, root in enumerate(finder.root) if x == root)

现在不需要执行find折叠整棵树。也不需要创建一个集合，因为它保证找到x的是唯一的。最后，不需要将该迭代器转换为列表。计算迭代器中的项目数就足够了。

于 2021-08-30T09:17:01.967 回答