Number of Islands II

union and find

Abstraction:

• objects
• Disjoint sets of objects
• find - are two objects in the same sets?
• union - replace sets containing two items by their union. simply speaking is to merge two sets

see here

two optimized mechanisms:

• weighted union-find
  • store the information of the tree's size
  • merge the small tree into the big tree
• compress the path
  • flatten the tree
  • so that the find() can run very fast
  • make every other node in path point to its grandparent

class Solution(object):
    def numIslands2(self, m, n, positions):
        """
        :type m: int
        :type n: int
        :type positions: List[List[int]]
        :rtype: List[int]
        """
        directions = [(1,0), (-1,0), (0,1), (0,-1)]
        union = Union()
        res = []

        for p in positions:
            union.add((p[0], p[1]))

            for dir in directions:
                tmp = (p[0]+dir[0], p[1]+dir[1])
                if tmp in union.id:
                    union.unite(tmp, (p[0], p[1]))

            res.append(union.cnt)

        return res


class Union(object):
    def __init__(self):
        self.id = {}
        self.weighted = {}
        self.cnt = 0

    def add(self, i):
        self.id[i] = i
        self.weighted[i] = 1
        self.cnt += 1

    def find(self, i):
        while i != self.id[i]:
            self.id[i] = self.id[self.id[i]]     ##### compress the path
            i = self.id[i]
        return i

    def unite(self, i, j):
        rooti = self.find(i)
        rootj = self.find(j)

        if rooti == rootj:
            return

        if self.weighted[rooti] > self.weighted[rootj]:   ###### weighted unite
            self.id[rootj] = rooti
            self.weighted[rooti] += 1
        else:
            self.id[rooti] = rootj
            self.weighted[rootj] += 1

        self.cnt -= 1