Leecode #947 移除最多的同行或同列石头

我们将石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。

每次 move 操作都会移除一块所在行或者列上有其他石头存在的石头。

请你设计一个算法，计算最多能执行多少次 move 操作？

示例

示例 1：

输入：stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
输出：5
示例 2：

输入：stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
输出：3
示例 3：

输入：stones = [[0,0]]
输出：0
 

提示：

1 <= stones.length <= 1000
0 <= stones[i][j] < 10000

解题思路

题目很抽象，当其实就是找连通图的个数，一共有2中方法：dfs和dsu（disjoint-set）

1. dfs

没有什么难度，遍历-压栈-弹出

import collections
class Solution:
    def removeStones(self, stones) -> int:
        X = collections.defaultdict(set)
        Y = collections.defaultdict(set)
        mmax = -1
        for x, y in stones:
            X[x].add(y)
            Y[y].add(x)
            mmax = max(mmax, x)
        
        count = 0
        for i in range(mmax+1):
            if i in X:
                count += 1
                stack = [i]
                while len(stack):
                    index = stack.pop()
                    Ys = X[index]
                    for j in Ys:
                        for k in Y[j]:
                            if k in X:
                                stack.append(k)
                    del X[index]
        return len(stones) - count

2. dsu

新知识点get。

并查集主要是find和union的操作（好像还有缩短路径的优化，这里没涉及到），题目x，y的范围在0-10000，所以可以用10000将它们隔开，用一个一维的数组来表示这个集合，主要的思想就是把x（0-10000）映射到y（10001-20000），在y空间上，不同节点还存在父子关系，最后只要数出父亲节点的个数就好了。

def removeStones(self, stones):
  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

          N = len(stones)
          dsu = DSU(20000)
          for x, y in stones:
            dsu.union(x, y + 10000)
            print({dsu.find(x) for x, y in stones})
            return N - len({dsu.find(x) for x, y in stones})