Python Union and Find solution (without DFS or BFS)


  • 0
    Z
    class Solution(object):
        def numIslands(self, grid):
            """
            :type grid: List[List[str]]
            :rtype: int
            """
            if not grid:
                return 0
            m=len(grid)
            n=len(grid[0])
            djset=[[0 for j in range(n+1)]for i in range(m+1)]
            id=1
            for i in range(m):
                for j in range(n):
                    if grid[i][j]=='1':
                        djset[i+1][j+1]=id
                        id+=1
            
            operation=self.getCommand(djset,m,n)
            
            union=[-1 for i in range(id)]
            for a,b in operation:
                classA=self.find(union,a)
                classB=self.find(union,a=b)
                if classA==classB:
                    continue
                self.union(union,classA,classB)
                    
            return self.countIsland(union)
            
        def countIsland(self,union):
            count=0
            for h in union[1:]:
                if h<0:
                    count+=1
            return count
        def union(self,union,classA,classB):
            if union[classA]<=union[classB]:
                    union[classA]+=union[classB]
                    union[classB]=classA
            else:
                    union[classB]+=union[classA]
                    union[classA]=classB
            
        def find(self,union,a):
            id=a
            x=union[id]
            while x>0:
                id=x
                x=union[id]
            return id
                
        def getCommand(self,djset,m,n):
            operation=[]
            for i in range(1,m+1):
                for j in range(1,n+1):
                    if djset[i][j]>0:
                        if djset[i-1][j]>0:
                            operation.append((djset[i][j],djset[i-1][j]))
                        if djset[i][j-1]>0:
                            operation.append((djset[i][j],djset[i][j-1]))
            return operation

Log in to reply
 

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