题目描述

题目求最多的操作次数，每次操作的要求是被选定要移除的石子所在行或者列必须还有其他的石子。采用并查集的思想，如果一个集合可以通过行或者列间接相连，那么存在一种顺序使得某一连通集合中只剩下一个石子。

为了防止行和列出现重复，对于列的值加上一个10000，因为x和y的范围都是10000，因此加上10000保证x和y的数值不会有重叠。然后开始合并能够连通的石子。答案等于 总石子数-集合数量

C++ 代码

class Solution {
public:
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    void uni(int x, int y)
    {
        int a = find(x), b = find(y);
        if (a != b) p[a] = b;
    }

    int p[20000]; // 数值的范围是2000
    unordered_set<int> list;
    int removeStones(vector<vector<int>>& stones) {
        for(int i = 0; i < 20000; i ++) p[i] = i;
        for(int i = 0; i < stones.size(); i ++) uni(stones[i][0],stones[i][1] + 10000);
        for(int i = 0; i < stones.size(); i ++) list.insert(find(stones[i][0]));
        return stones.size() - list.size();
    }
};