Question

Code

class Solution:
    def removeStones(self, stones: List[List[int]]) -> int:

        '''
            dfs on each of group connect by x-axis or y-axis, this group can be trimmed from the leaf node, to only one root node remains
        '''
        
        # x_adj = defaultdict(list)
        # y_adj = defaultdict(list)

        # for x, y in stones:
        #     x_adj[x].append((x, y))
        #     y_adj[y].append((x, y))

        # visited = set()
        # group = 0


        # def dfs(cur_x, cur_y):
        #     if (cur_x, cur_y) in visited:
        #         return

        #     visited.add((cur_x, cur_y))

        #     for new_x, new_y in x_adj[cur_x]:
        #         dfs(new_x, new_y)

        #     for new_x, new_y in y_adj[cur_y]:
        #         dfs(new_x, new_y)

        # for x, y in stones:
        #     if (x, y) not in visited:
                
        #         dfs(x, y)
        #         group += 1

        # return len(stones) - group

        OFFSET = 10001

        par = {}

        def find(x):
            if x not in par:
                par[x] = x
                return x

            while x != par[x]:
                x = par[par[x]]

            return x

        def union(x, y):
            
            r1, r2 = find(x), find(y)

            if r1 != r2:
                par[r1] = r2

        for i, j in stones:
            union(i, j + OFFSET)
            # union(i, ~j)

        roots = set()

        for key in par:
            roots.add(find(key))


        return len(stones) - len(roots)