CODEWITHSUNDEEP
algorithmgraphdisjoint-setsunion-finddisjoint-union
Intern
Intern

Reputation: 39

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

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

Question link

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]))

Upvotes: -1

Views: 68

Answers (2)

trincot
trincot

Reputation: 351128

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.

Upvotes: 0

Intern
Intern

Reputation: 39

Ah ha! Found the answer

The reason why it was returning more distinct root than it actually have is due to the fact the root for those vertices hasn't got updated yet

All I gotta do is add a loop at the end to do find() operation on each vertex to update the root value for all of its parents

The find() operation will traverse recursively to the root node, and on the way back will update the root value of all node on the way

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

Thank you all!

Upvotes: 0

Related Questions