Union Find in Python


  • 0
    T
    class Solution(object):
        def numIslands(self, grid):
            """
            :type grid: List[List[str]]
            :rtype: int
            """
            if not grid:
                return 0
            m, n, count = len(grid), len(grid[0]), 0
            roots = [-1 for i in xrange(m*n)]
            pos = [(0, 1), (0, -1), (1, 0), (-1, 0)]
            for i in xrange(m):
                for j in xrange(n):
                    if grid[i][j] == '1':
                        count += 1
                        root = i*n+j
                        roots[root] = root
                        for p in pos:
                            x = i + p[0]
                            y = j + p[1]
                            neighbor = x*n + y
                            if x < 0 or x >= m or y < 0 or y >= n or grid[x][y] == '0' or roots[neighbor] == -1:
                                continue
                            neighborRoot = self.findRoot(roots, neighbor)
                            if neighborRoot != root:
                                roots[root] = neighborRoot
                                root = neighborRoot
                                count -= 1
            return count
        
        def findRoot(self, roots, root):
            while roots[root] != root:
                roots[root] = roots[roots[root]]
                root = roots[root]
            return root
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.