class Islands:

''' This class is a variant of weighted quick union.

'''

# Reference: http://algs4.cs.princeton.edu/15uf/

# http://algs4.cs.princeton.edu/15uf/QuickUnionUF.java.html

parent_ = None

size_ = None

components_ = 0

def __init__(self, nodes_count):

# parent_[i] is the index of i(th) node's parent.

# If parent_[i] is -1, the i(th) node is

# either water

# or root of some tree.

self.parent_ = [-1] * nodes_count

# size_[i] is the size of the (sub)tree, whose root is the i(th) node.

# If size_[i] is 0, the i(th) node is not land.

self.size_ = [1] * nodes_count

# The number of islands.

self.components_ = 0

def _root(self, node):

''' Find the root node of the tree, which contains the given node.

'''

root = node

while self.parent_[root] != -1:

root = self.parent_[root]

return root

def count(self):

''' Return the number of trees in this forest, that is, the number

of islands.

'''

return self.components_

def union(self, node1, node2):

''' Connect the island with node1 and island with node2 into one

island.

'''

# Did not check whether the nodes are water or land. Caller should make

# sure the they are land.

root1 = self._root(node1)

root2 = self._root(node2)

# The nodes are in one tree.

if root1 == root2: return

size1 = self.size_[root1]

size2 = self.size_[root2]

if size1 <= size2:

# Attach the tree with ndoe1 to the tree with node2

self.parent_[root1] = root2

self.size_[root2] += self.size_[root1]

else:

# Attach the tree with ndoe2 to the tree with node1

self.parent_[root2] = root1

self.size_[root1] += self.size_[root2]

self.components_ -= 1

return

def add_land(self, node):

''' Convert this cell from water to land.

'''

self.parent_[node] = -1

self.size_[node] = 1

self.components_ += 1

class Solution:

# @param {character[][]} grid

# @return {integer}

def numIslands(self, grid):

if len(grid) == 0 or len(grid[0]) == 0: return 0

geo = Islands(len(grid) * len(grid[0]))

# These two for loops could be combined to one for loop. However, we

# keep them separated for better understanding.

# Initialize each land cell.

for row in xrange(len(grid)):

for column in xrange(len(grid[0])):

if grid[row][column] == "1":

node_id = row * len(grid[0]) + column

geo.add_land(node_id)

# Combine all adjacent lands into an island.

for row in xrange(len(grid)):

for column in xrange(len(grid[0])):

if grid[row][column] == "0":

# This is a water cell.

continue

else:

# This is a land cell.

node1_id = row * len(grid[0]) + column

if row != len(grid) - 1 and grid[row + 1][column] == "1":

node2_id = (row + 1) * len(grid[0]) + column

geo.union(node1_id, node2_id)

if column != len(grid[0]) - 1 and grid[row][column + 1] == "1":

node2_id = row * len(grid[0]) + (column + 1)

geo.union(node1_id, node2_id)

return geo.count()