'''
keys: union find
Solutions:
Similar: 684
T: O(n*n*alpha(n)), n as the length of the grid, and 
α is the Inverse-Ackermann function (if we were to use union-find by rank.)
S: O(n*n)
'''
from typing import List


class DSU:
    def __init__(self, N):
        self.p = list(range(N))
    
    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, x, y):
        xr = self.find(x)
        yr = self.find(y)
        self.p[xr] = yr
            

class Solution:
    # like this
    # \0  /
    # 1\/2
    #  /\
    # /3 \
    def regionsBySlashes(self, grid: List[str]) -> int:
        N = len(grid)
        dsu = DSU(4 * N * N)
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                root = 4 * (r*N + c) # 4 means 4 triangles in a grid
                val = grid[r][c]
                if val == '/':
                    dsu.union(root + 0, root + 3)
                    dsu.union(root + 1, root + 2)
                if val == '\\':
                    dsu.union(root + 0, root + 1)
                    dsu.union(root + 2, root + 3)
                if val == ' ':
                    dsu.union(root + 0, root + 1)
                    dsu.union(root + 1, root + 2)
                    dsu.union(root + 2, root + 3)
                    
                # merge neigboring north/south triangles
                # not first row and not last row
                if r < N-1: dsu.union(root + 2, (root+4*N) + 0)
                # if r >= 1: dsu.union(root + 0, (root-4*N) + 3)
                # merge neigboring east/west triangles
                # not first col and not last col
                if c < N-1: dsu.union(root + 1, (root+4) + 3)
                # if c >= 1: dsu.union(root + 1, (root-4) + 2)

        return sum(dsu.find(x) == x for x in range(4*N*N))
    
    
    
    # lee's version
    def regionsBySlashes1(self, grid: List[str]) -> int:
        f = {}
        def find(x):
            f.setdefault(x, x)
            if x != f[x]:
                f[x] = find(f[x])
            return f[x]
        def union(x, y):
            f[find(x)] = find(y)

        for i in range(len(grid)):
            for j in range(len(grid)):
                if i:
                    union((i - 1, j, 2), (i, j, 0))
                if j:
                    union((i, j - 1, 1), (i, j, 3))
                if grid[i][j] != "/":
                    union((i, j, 0), (i, j, 1))
                    union((i, j, 2), (i, j, 3))
                if grid[i][j] != "\\":
                    union((i, j, 3), (i, j, 0))
                    union((i, j, 1), (i, j, 2))
        return len(set(map(find, f)))
        