Number of Islands II

A 2d grid map of m rows and n columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land. Given a list of positions to operate, count the number of islands after each addLand operation. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example:

Given m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]]. Initially, the 2d grid grid is filled with water. (Assume 0 represents water and 1 represents land).

We return the result as an array: [1, 1, 2, 3]

https://leetcode.com/problems/number-of-islands-ii/

思路：这道题是union find的经典题型了。看代码就能make sense了。我只能说感谢乐神。乐神我是你的粉丝！我优化了一点点乐神的代码。一样ac了。在find的时候，其实只用compress i的parents就行了。

class Solution(object):
    def numIslands2(self, m, n, positions):
        """
        :type m: int
        :type n: int
        :type positions: List[List[int]]
        :rtype: List[int]
        """
        ans = []
        islands = Union()
        for p in map(tuple, positions):
            islands.add(p)
            for dp in (0, 1), (0, -1), (1, 0), (-1, 0):
                q = (p[0] + dp[0], p[1] + dp[1])
                if q in islands.dic:
                    islands.unite(p, q)
            ans += [islands.cnt]
        return ans

class Union(object):
    def __init__(self):
        self.dic = {}
        self.sz = {}
        self.cnt = 0

    def add(self, i):
        self.dic[i] = i
        self.sz[i] = 1
        self.cnt += 1

    def find(self, i):
        while self.dic[i]!= self.dic[self.dic[i]]:
            self.dic[i] = self.dic[self.dic[i]]
        return self.dic[i]

    def unite(self, p, q):
        i, j = self.find(p), self.find(q)
        if i==j:
            return
        if self.sz[i] > self.sz[j]:
            i, j = j, i
        self.dic[i] = j
        self.sz[j] += self.sz[i]
        self.cnt -= 1


so = Solution()
p = [[0,1],[1,2],[2,1],[1,0],[0,2],[0,0],[1,1]]
a = so.numIslands2(3,3,p)
print(a)