Question: https://leetcode.com/problems/number-of-islands/
Question Name: Number of Islands
A variant of weighted quick union.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 | 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() |