LeetCode 947. 移除最多的同行或同列石头

题目描述

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

如果一块石头的同行或者同列上有其他石头存在，那么就可以移除这块石头。

给你一个长度为 $n$ 的数组 stones ，其中 stones[i] = [xi, yi] 表示第 $i$ 块石头的位置，返回 可以移除的石子 的最大数量。

示例 1

输入：stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
输出：5
解释：

一种移除 5 块石头的方法如下所示：
1. 移除石头 [2,2] ，因为它和 [2,1] 同行。
2. 移除石头 [2,1] ，因为它和 [0,1] 同列。
3. 移除石头 [1,2] ，因为它和 [1,0] 同行。
4. 移除石头 [1,0] ，因为它和 [0,0] 同列。
5. 移除石头 [0,1] ，因为它和 [0,0] 同行。
石头 [0,0] 不能移除，因为它没有与另一块石头同行/列。

示例 2

输入：stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
输出：3
解释：

一种移除 3 块石头的方法如下所示：
1. 移除石头 [2,2] ，因为它和 [2,0] 同行。
2. 移除石头 [2,0] ，因为它和 [0,0] 同列。
3. 移除石头 [0,2] ，因为它和 [0,0] 同行。
石头 [0,0] 和 [1,1] 不能移除，因为它们没有与另一块石头同行/列。

示例 3

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

[0,0] 是平面上唯一一块石头，所以不可以移除它。

题解

题目意思是，如果同一行或同一列有多个石头，那么可以“消去”其他石头只留下一个，求最多能消去多少个。

首先进行名词定义：

关系: 两个石头在同一行和同一列，则说明这两个石头存在关系
弱关系: 两个石头不在同一行和同一列，但是可以通过多个关系的传递，实现弱关系
同类: 所有具有弱关系的石头分类
消去: 如果两个石头具有关系，那么可以从图上删除其中一个石头

首先举一个简单的例子，如图， $0$ 和 $1$ 在同一行， $0$ 和 $2$ 在同一列，并且在这种“消去”时，应该先消去 $1$ 或 $2$ ，再消去 $0$ 。
也即最多可以消去 $2$ 个

看到这道题的思路是：把所有同一行同一列的分成一类，然后从“边缘”开始删，直到删到不能再删

如果所有的石头都具有关系，那么显然可以直接消去至只剩下一个。
如果石头之间存在弱关系，可以先消去边缘（只和一个石头存在关系）的石头，重复该过程直到剩下的石头都和多于一个的石头存在关系。
如果将关系以连线表示，说明这时石头之间“成环”。由于环中所有石头都拥有两个以上的关系，因此每一个石头仍然保持可消去的特点，只需要考虑会不会存在任意选的石头，把原本的一个分类划分成两个分类，导致这种情况的原因是多个环共用一个石头，删去该石头后多个环弱连接丧失。
但同理也可反推，只需要保持这个石头存在，那么所有的环都可被消去。
更复杂的情况也可简化至这种情况。

于是，可以得到结论：同类的石头，必定可以被消去至只剩一个

也即，在消去至只剩下一个的情况中，弱关系 和关系等价。

那么只需要将所有的石头进行分类即可，每个分类留一个就是最后剩余的石头。

求 事物之间存在连接和弱连接关系 使用 并查集

这道题最大的意义是，确定 并查集 的使用情景，在遇到 弱连接分类问题 时，就可以尝试一下

附上并查集核心代码

f = [i for i in range(n)]
def getF(x):
    '''
    获得 x 所在分类的代表
    带路径压缩，尽可能使得每个元素都直指代表
    '''
    f[x] = x if f[x] == x else getF(f[x])
    return f[x]
def connect(i, j):
    '''
    i 和 j 存在弱连接
    '''
    f[getF(i)] = getF(j)

代码

class Solution:
    def removeStones(self, stones: List[List[int]]) -> int:
        n = len(stones)
        f = [i for i in range(n)]
        def getF(x):
            f[x] = x if f[x] == x else getF(f[x])
            return f[x]
        def connect(i, j):
            f[getF(i)] = getF(j)
        
        dx = {}
        dy = {}
        for i, stone in enumerate(stones):
            x, y = stone

            sx = dx.get(x, None)
            if sx == None:
                dx[x] = i
            else:
                connect(i, sx)
            
            sy = dy.get(y, None)
            if sy == None:
                dy[y] = i
            else:
                connect(i, sy)
        
        count = 0
        for i in range(n):
            if getF(i) == i:
                count += 1

        return n - count