1. 题目

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

每次 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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/most-stones-removed-with-same-row-or-column
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

参考 数据结构–并查集（Disjoint-Set）

• 把行号、列号看成一个单元
• 用并查集把每个点的行列merge
• 最后查找都有点有几个单元，点的个数减去单元个数就是能移走的石子

class dsu
{
    vector<int> f;
public:
    dsu(int n)
    {
        f.resize(n);
        for(int i = 0; i < n; ++i)
            f[i] = i;
    }
    void merge(int a, int b)
    {
        int fa = find(a), fb = find(b);
        f[fa] = fb;
    }
    int find(int a)
    {
        int origin = a;
        while(f[a] != a)
        {
            a = f[a];
        }
        return f[origin] = a;
    }
};
class Solution {
public:
    int removeStones(vector<vector<int>>& stones) {
        dsu u(20000);
        unordered_set<int> s;
        for(int i = 0; i < stones.size(); ++i)
            u.merge(stones[i][0], stones[i][1]+10000);
        for(int i = 0; i < stones.size(); ++i)
            s.insert(u.find(stones[i][0]));
        return stones.size()-s.size();
    }
};

60 ms 19.6 MB