1905. Count Sub Islands - cocoder39/coco39_LC GitHub Wiki

1905. Count Sub Islands

Option 1: DFS

pitfall: I attempted to terminate dfs() call as soon as res becomes 0. The consequence is that one big island in grid2 will be split to multiple small islands just because the corresponding grid in grid1 doesn't match

class Solution:
    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
        m, n = len(grid1), len(grid1[0])

        def dfs(i, j):
            if not (0 <= i < m and 0 <= j < n and grid2[i][j] == 1): 
                return True
            
            grid2[i][j] = 0
            
            res = grid1[i][j]
            for di, dj in [0, -1], [0, 1], [-1, 0], [1, 0](/cocoder39/coco39_LC/wiki/0,--1],-[0,-1],-[-1,-0],-[1,-0):
                res &= dfs(i + di, j + dj)
            return res
            
        count = 0
        for i in range(m):
            for j in range(n):
                if grid2[i][j]:
                    count += dfs(i, j)
        return count

Option 2: union find

class UnionFind:
    def __init__(self):
        self.parent = {}
        self.size = {}
    
    def union(self, x1, y1, x2, y2):
        rootX1, rootY1 = self.find(x1, y1)
        rootX2, rootY2 = self.find(x2, y2)
        if rootX1 != rootX2 or rootY1 != rootY2:
            size1 = self.size[(rootX1, rootY1)]
            size2 = self.size[(rootX2, rootY2)]
            
            if size1 < size2:
                self.parent[(rootX1, rootY1)] = (rootX2, rootY2)
                self.size[(rootX2, rootY2)] = size1 + size2
            else:
                self.parent[(rootX2, rootY2)] = (rootX1, rootY1)
                self.size[(rootX1, rootY1)] = size1 + size2
    
    def find(self, x, y):
        if (x, y) not in self.parent:
            self.parent[(x, y)] = (x, y)
            self.size[(x, y)] = 1
            return (x, y)
    
        while (x, y) != self.parent[(x, y)]:
            (x, y) = self.parent[self.parent[(x, y)]]
        return (x, y)
        

class Solution:
    
    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
        m, n = len(grid1), len(grid2[0])
        
        def buildUf(grid):
            DIR = [(-1, 0), (0, -1)]
            uf = UnionFind()
            for i in range(m):
                for j in range(n):
                    if grid[i][j]:
                        uf.find(i, j)
                        for dx, dy in DIR:
                            x, y = i + dx, j + dy
                            if 0 <= x < m and 0 <= y < n and grid[x][y]:
                                uf.union(i, j, x, y)
            return uf
        
        def buildGroup(grid, uf):
            res = collections.defaultdict(set)
            for i in range(m):
                for j in range(n):
                    if grid[i][j]:
                        rootX, rootY = uf.find(i, j)
                        res[(rootX, rootY)].add((i, j))
            return res
            
        uf1, uf2 = buildUf(grid1), buildUf(grid2)
        groups1, groups2 = buildGroup(grid1, uf1), buildGroup(grid2, uf2)
        #print(groups1)
        #print(groups2)
        
        res = 0
        for root in groups2:
            if not grid1[root[0]][root[1]]:
                continue
            
            group1 = groups1[uf1.find(root[0], root[1])]
            group2 = groups2[root]
            count = 0
            
            for grid in group2:
                if grid in group1:
                    count += 1
            if count == len(group2):
                res += 1
        return res