1def num_islands_ii(m, n, positions):
2 parent = {}
3 islands = 0
4 grid = [[0]*n for _ in range(m)]
5
6 def find(x):
7 if parent[x] != x:
8 parent[x] = find(parent[x])
9 return parent[x]
10
11 def union(x, y):
12 rx, ry = find(x), find(y)
13 if rx != ry:
14 parent[rx] = ry
15 return True
16 return False
17
18 ans = []
19 for r, c in positions:
20 if grid[r][c] == 1:
21 continue
22 grid[r][c] = 1
23 parent[(r, c)] = (r, c)
24 islands += 1
25 for dr, dc in [(-1,0), (1,0), (0,-1), (0,1)]:
26 nr, nc = r + dr, c + dc
27 if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
28 if union((r, c), (nr, nc)):
29 islands -= 1
30 ans.append(islands)
31 return ans