I try using the Union find method for this question but not passing this case, could somebody may be give me an insight to why that is?
find() : for find method there is path compression union() : for union there is union by rank
So far pass 108/113 cases Return 5 Expected 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]))
Although launching find on every node in the union-find tree will solve the issue, it is more efficient to just count the number of actual roots, i.e. those nodes that have a self-reference via the root attribute:
return sum(1 for x, root in enumerate(finder.root) if x == root)
There is no need now to execute find to collapse the whole tree. Also it is not needed to create a set, as it is guaranteed that the found x are unique. And finally, it is not needed to turn that iterator into a list. Counting the number of items in the iterator is enough.