C++刷LeetCode（947. 移除最多的同行或同列石头）【并查集】
题目描述：n 块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。
如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头。
给你一个长度为 n 的数组 stones ，其中 stones = 表示第 i 块石头的位置，返回 可以移除的石子 的最大数量。
示例 1：
输入：stones = [,,,,,]
输出：5
解释：一种移除 5 块石头的方法如下所示：
1. 移除石头 ，因为它和 同行。
2. 移除石头 ，因为它和 同列。
3. 移除石头 ，因为它和 同行。
4. 移除石头 ，因为它和 同列。
5. 移除石头 ，因为它和 同行。
石头 不能移除，因为它没有与另一块石头同行/列。
示例 2：
输入：stones = [,,,,]
输出：3
解释：一种移除 3 块石头的方法如下所示：
1. 移除石头 ，因为它和 同行。
2. 移除石头 ，因为它和 同列。
3. 移除石头 ，因为它和 同行。
石头 和 不能移除，因为它们没有与另一块石头同行/列。
示例 3：
输入：stones = []
输出：0
解释： 是平面上唯一一块石头，所以不可以移除它。
提示：
1 <= stones.length <= 1000
0 <= xi, yi <= 104
不会有两块石头放在同一个坐标点上
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/most-stones-removed-with-same-row-or-column
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
private:
int father;
public:
int find_root(int x){
if(father == x)return x;
return find_root(father);
}
void merge(int x, int y){
int temp1 = find_root(x);
int temp2 = find_root(y);
if(temp1 != temp2)father = temp2;
}
int removeStones(vector<vector<int>>& stones) {
//并查集
int len = stones.size();
//初始化father
for(int i = 0; i < len; i++){
father] = stones;
father + 10000] = stones + 10000;
}
//合并
for(int i = 0; i < len; i++){
merge(stones, stones+10000);
}
//计算
set<int>store;
for(int i = 0; i < len; i++){
store.insert(find_root(stones));
}
return len - store.size();
}
};
参考链接：https://leetcode-cn.com/problems/most-stones-removed-with-same-row-or-column/solution/bing-cha-ji-de-ling-huo-ying-yong-an-zhao-zuo-biao/
页:
[1]