题目描述

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

现在，move 操作将会移除与网格上的某一块石头共享一列或一行的一块石头。

我们最多能执行多少次 move 操作？

样例

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

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

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

注意

• 1 <= stones.length <= 1000
• 0 <= stones[i][j] < 10000

算法

(并查集) $O(n (\log n + \alpha(n)))$

1. 每个石头看做一个点，将在同一行或一列的石头之间连边，这样可以形成若干个连通块；最终答案为每个连通块的大小减去 1 后的求和。
2. 可以证明，在同一个连通块内，总存在一种方法，可以将其内部 move 到只剩下一块石头。
3. 求连通块可以同并查集。

时间复杂度

• 通过先横坐标排序，然后纵坐标排序，排序以后同一行的石头中，每个只需要向下一个石头连边即可。
• 并查集的时间复杂度为 $O(\alpha(n))$，故总时间复杂度为 $O(n (\log n + \alpha(n)))$。

C++ 代码

bool cmp1(const vector<int> &x, const vector<int> &y) {
    return x[0] < y[0];
}

bool cmp2(const vector<int> &x, const vector<int> &y) {
    return x[1] < y[1];
}


class Solution {
public:

    vector<int> f, sz;

    int find(int x) {
        return x == f[x] ? x : f[x] = find(f[x]);
    }

    void uni(int x, int y) {
        int fx = find(x), fy = find(y);

        if (fx != fy) {
            if (sz[fx] < sz[fy]) {
                f[fx] = fy;
                sz[fy] += sz[fx];
            }
            else {
                f[fy] = fx;
                sz[fx] += sz[fy];
            }
        }
    }

    int removeStones(vector<vector<int>>& stones) {
        int n = stones.size();
        f = vector<int>(n);
        sz = vector<int>(n);

        for (int i = 0; i < n; i++) {
            f[i] = i;
            sz[i] = 1;
            stones[i].push_back(i);
        }

        sort(stones.begin(), stones.end(), cmp1);

        for (int i = 0; i < n; i++) {
            if (i > 0 && stones[i - 1][0] == stones[i][0]) {
                uni(stones[i - 1][2], stones[i][2]);
            }
        }

        sort(stones.begin(), stones.end(), cmp2);

        for (int i = 0; i < n; i++) {
            if (i > 0 && stones[i - 1][1] == stones[i][1]) {
                uni(stones[i - 1][2], stones[i][2]);
            }
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (i == find(i))
                ans += sz[i] - 1;
        }

        return ans;
    }
};