To be honest, I did find Union Find (Disjoint Sets) daunting at first but watching some videos and implementing it a couple times for solving problems has made me realize that it's rather simple. On that note, here's my implementation for this problem:

( As I don't have a subscription I wasn't able to verify my solution on OJ. I did some testing and it seems to be working fine though. Let me know if you see any bugs. Thanks.)

Some notes:

I index each row,column and store those as the keys being process in the disjoint set
This implementation does not treat two diagonally adjacent islands as one island. This could easily be handled by changing the 'direc' (directions) variable to check for diagonals as well.
class Islands:
def __init__(self, m, n):
self.grid = [[0] * m for _ in range(n)]
self.m = m
self.n = n
self.ranks = {}
self.parents = {}
self.cnt = 0
self.direc = {(0, 1), (0, -1), (1, 0), (-1, 0)}
def addLand(self, r, c):
if self.valid_coord(r, c) and self.grid[r][c] == 0:
self.grid[r][c] = 1
self.make_set(r, c)
self.check_position(r, c)
return True
return False
def make_set(self, r, c):
ind = self.indexify(r, c)
self.ranks[ind] = 0
self.parents[ind] = ind
self.cnt += 1 # new singular island
def union(self, u, v):
U, V = self.find_parent(u), self.find_parent(v)
# This is more for a typical implementation of disjoint sets. Shouldn't happen in this problem though.
if U == V: return False
# here on we're unioning two sets thus island count is decremented
self.cnt -= 1
if self.ranks[U] < self.ranks[V]:
self.ranks[V] += 1
self.parents[U] = V
else:
self.ranks[U] += 1
self.parents[V] = U
def find_parent(self, u):
if self.parents[u] == u: return u
self.parents[u] = self.find_parent(self.parents[u]) # path compression
return self.parents[u]
def valid_coord(self, r, c):
return 0 <= r < self.n and 0 <= c < self.m
def check_position(self, r, c):
ind = self.indexify(r, c)
for dr, dc in self.direc:
r_, c_ = r + dr, c + dc
if self.valid_coord(r_, c_) and self.grid[r_][c_] == 1:
self.union(ind, self.indexify(r_, c_))
def indexify(self, r, c):
return r * self.m + c
def get_island_count(self):
return self.cnt
if __name__ == "__main__":
I = Islands(3, 3) # 3x3 grid
I.addLand(0, 0)
print(I.get_island_count()) # 1
I.addLand(0, 1)
print(I.get_island_count()) # 1
I.addLand(1, 2)
print(I.get_island_count()) # 2
I.addLand(2, 1)
print(I.get_island_count()) # 3
I.addLand(1, 1)
print(I.get_island_count()) # 1