1905. Count Sub Islands - Explanation

class Solution:
    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
        ROWS, COLS = len(grid1), len(grid1[0])
        visit = set()

        def dfs(r, c):
            if (min(r, c) < 0 or r == ROWS or c == COLS or
                grid2[r][c] == 0 or (r, c) in visit):
                return True

            visit.add((r, c))
            res = grid1[r][c]

            res &= dfs(r - 1, c)
            res &= dfs(r + 1, c)
            res &= dfs(r, c - 1)
            res &= dfs(r, c + 1)
            return res

        count = 0
        for r in range(ROWS):
            for c in range(COLS):
                if grid2[r][c] and (r, c) not in visit:
                    count += dfs(r, c)
        return count

class Solution:
    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
        ROWS, COLS = len(grid1), len(grid1[0])
        visit = [[False] * COLS for _ in range(ROWS)]
        directions = [1, 0, -1, 0, 1]

        def bfs(r, c):
            queue = deque([(r, c)])
            visit[r][c] = True
            res = True

            while queue:
                r, c = queue.popleft()
                if grid1[r][c] == 0:
                    res = False

                for i in range(4):
                    nr, nc = r + directions[i], c + directions[i + 1]
                    if 0 <= nr < ROWS and 0 <= nc < COLS and not visit[nr][nc] and grid2[nr][nc]:
                        visit[nr][nc] = True
                        queue.append((nr, nc))
            return res

        count = 0
        for r in range(ROWS):
            for c in range(COLS):
                if grid2[r][c] == 1 and not visit[r][c]:
                    if bfs(r, c):
                        count += 1
        return count

class DSU:
    def __init__(self, n):
        self.Parent = list(range(n + 1))
        self.Size = [1] * (n + 1)

    def find(self, node):
        if self.Parent[node] != node:
            self.Parent[node] = self.find(self.Parent[node])
        return self.Parent[node]

    def union(self, u, v):
        pu = self.find(u)
        pv = self.find(v)
        if pu == pv:
            return False
        if self.Size[pu] < self.Size[pv]:
            pu, pv = pv, pu
        self.Size[pu] += self.Size[pv]
        self.Parent[pv] = pu
        return True

class Solution:
    def countSubIslands(self, grid1, grid2):
        ROWS, COLS = len(grid1), len(grid1[0])
        N = ROWS * COLS
        dsu = DSU(N)

        def getId(r, c):
            return r * COLS + c

        land = unions = 0
        for r in range(ROWS):
            for c in range(COLS):
                if not grid2[r][c]:
                    continue
                land += 1
                if r + 1 < ROWS and grid2[r + 1][c]:
                    unions += dsu.union(getId(r, c), getId(r + 1, c))
                if c + 1 < COLS and grid2[r][c + 1]:
                    unions += dsu.union(getId(r, c), getId(r, c + 1))
                if not grid1[r][c]:
                    unions += dsu.union(getId(r, c), N)

        return land - unions