305. Number of Islands II
一道union-find的题目，这类题目只要找准谁是boss就可以了，剩下的就去套模板
class Solution(object):
# @param {int} n an integer
# @param {int} m an integer
# @param {Pint[]} operators an array of point
# @return {int[]} an integer array
def numIslands2(self, n, m, operators):
# Write your code here
res = []
self.h = {}
self.count = 0
for p in operators:
i, j = p
if (i, j) in self.h:
continue
self.count += 1
self.h[(i, j)] = (i, j)
for x, y in [[i-1, j], [i+1, j], [i, j-1], [i, j+1]]:
if 0 <= x < n and 0 <= y < m and (x, y) in self.h:
self.union((i,j), (x,y))
res.append(self.count)
return res
def union(self, n1, n2):
f1 = self.find(n1)
f2 = self.find(n2)
if f1 != f2:
self.h[f2] = f1
self.count -= 1
def find(self, n):
if n == self.h[n]:
return n
self.h[n] = self.find(self.h[n])
return self.h[n]
