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

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

题目描述：

$n$ 块石头放在二维平面中整点上。每个坐标点上最多只能有一块石头。如果有一块石头的同行同列上有其他石头存在，那么就是可以移出这块石头。给你一个长度为 $n$ 的数组 $stones$ ，其中 $stones[i] = [x_i,y_i]$ 表示第 $i$ 块石头的位置，返回可以移除的石子的最大数量。

数据范围：

$1\le n \le 1000;0\le x_i,y_i\le 10^4$

题解：

将行和列的编号作为初始点集，如果一个点的坐标为 $[x_i,y_i]$ ，那么需要使用并查集合并行 $x_i$ 与列 $y_i$ 。一个连通块内的所有的点，可以通过调整顺序删的只剩一个点，按照依赖传递的方向删。因此只需要维护有多少个连通块即可，答案就是 $n - count$ 。就是因为点的坐标范围比较大，需要使用离散化处理。

代码：

auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    struct UF
    {
        vector<int> fa;
        int count;
        UF(int n) : fa(n), count(n)
        {
            for (int i = 0; i < n; ++i)
                fa[i] = i;
        }
        int find(int u) { return u == fa[u] ? u : fa[u] = find(fa[u]); }
        void unite(int u, int v)
        {
            int up = find(u), vp = find(v);
            if (up != vp)
            {
                fa[up] = vp;
                count--;
            }
        }
        bool connect(int u, int v) { return find(u) == find(v); }
        int getCount() { return count; }
    };
    int removeStones(vector<vector<int>> &stones)
    {
        int n = stones.size();
        unordered_map<int, int> mp;
        int cnt = 0;
        for (int i = 0; i < n; ++i)
        {
            int &x = stones[i][0], &y = stones[i][1];
            y += 10001;
            if (!mp.count(x)) x = mp[x] = cnt++;
            else x = mp[x];
            if (!mp.count(y)) y = mp[y] = cnt++;
            else y = mp[y];
        }
        UF uf(cnt);
        for (int i = 0; i < n; ++i)
        {
            int x = stones[i][0], y = stones[i][1];
            uf.unite(x, y);
        }
        return n - uf.getCount();
    }
};