LeetCode 947. 移除最多的同行或同列石头（并查集）

示例 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

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();
    }
};