我尝试对这个问题使用 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]))