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()