Leetcode 省份数未通过边缘案例最后几个边缘案例

Question

我尝试使用 Union find 方法来解决这个问题，但没有通过这个案例，有人可以告诉我这是为什么吗？

find() : 对于 find 方法有路径压缩 union() ：对于 union 有 union by rank

目前通过108/113例 Return 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]))

Answer 1

啊哈！找到答案

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

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

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

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

谢谢大家！

Answer 2

虽然在联合查找树中的每个节点上启动 find 将解决问题，但只计算实际根的数量更有效，即那些通过root 属性：

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

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

Leetcode 省份数未通过边缘案例最后几个边缘案例

Leetcode Number of Province not passing edge case last few edge case

algorithm

graph

disjoint-union

disjoint-sets

union-find