Lc803

class Solution:
    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:
        """ tc O(R*C + H) , H is len of hits. 
        
        """
        
        r = len(grid)
        c = len(grid[0])
        
        # 1. set connected grid to 2, and 2. remember connected value 
        def dfs(i,j):
            #(1) grid[i][j] == 1:  set to 2, within valid bound, accumutive sum,  (2) grid[i][j] != 1   => return 0 
            if grid[i][j] == 1:
                grid[i][j] = 2
                res = 1
                for x,y in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
                    if 0<= x < r and 0 <= y < c and grid[x][y] == 1:
                        res += dfs(x,y)
                return res
            return 0
            
            
        #check current pos connected to ceiling/ no-failing
        def is_connected(i,j):
            # (1) (i,j) is ceiling. (2) (i,j) neighbour grid value == 2 
            return i == 0 or any([0<= x < r and 0 <= y < c and  grid[x][y] == 2 for x,y in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]])
            
        # step1: remove hit  
        for h in hits:
            grid[h[0]][h[1]] -= 1 
        
        # step2: connect ceil 
        for i in range(c):
            dfs(0,i)
        
        # step3: reversely put back hit, do dfs, update res 
        res = [0] * len(hits)
        for k in range(len(hits)-1,-1,-1):
            x,y = hits[k][0],hits[k][1]
            grid[x][y]  +=  1
            if grid[x][y] == 1 and is_connected(x,y):
                res[k] = dfs(x,y) -1 
        return res 

class UF:
    def __init__(self,n):
        self.p = list(range(n))
        self.rank = [1] * n
        
    def find(self,u):
        if u != self.p[u]:
            self.p[u] = self.find(self.p[u])
        return self.p[u]
    
    def union(self,u,v):
        pv,pu = self.find(v), self.find(u)
        if pv == pu:
            return True 
        elif self.rank[pv] >= self.rank[pu]:
            self.p[pu] = self.pv
            self.rank[pv] += self.rank[pu]
        else:
            self.p[pv] = self.pu
            self.rank[pu] += self.rank[pv]
        return False
        
        
class Solution:
    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:
        r = len(grid)
        c = len(grid[0])
        # init UF
        uf = UF(r*c)
        for i in range(1,c):
            if grid[0][c] == 1 and grid[0][c-1] == 1: 
                union(c,c-1)
        
        # union bricks below
        
        
        # loop through hits checki its left,right, down , if they only connected with current hit, if yes, set neighbour's parent into itself and neighbour value ==0  cnt += 1 
        # each hit after it expand the sourroundings, append cnt into res