题目描述947. 移除最多的同行或同列石头 - 力扣LeetCoden块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。如果一块石头的同行或者同列上有其他石头存在那么就可以移除这块石头。给你一个长度为n的数组stones其中stones[i] [xi, yi]表示第i块石头的位置返回可以移除的石子的最大数量。示例 1输入stones [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]输出5解释一种移除 5 块石头的方法如下所示 1. 移除石头 [2,2] 因为它和 [2,1] 同行。 2. 移除石头 [2,1] 因为它和 [0,1] 同列。 3. 移除石头 [1,2] 因为它和 [1,0] 同行。 4. 移除石头 [1,0] 因为它和 [0,0] 同列。 5. 移除石头 [0,1] 因为它和 [0,0] 同行。 石头 [0,0] 不能移除因为它没有与另一块石头同行/列。示例 2输入stones [[0,0],[0,2],[1,1],[2,0],[2,2]]输出3解释一种移除 3 块石头的方法如下所示 1. 移除石头 [2,2] 因为它和 [2,0] 同行。 2. 移除石头 [2,0] 因为它和 [0,0] 同列。 3. 移除石头 [0,2] 因为它和 [0,0] 同行。 石头 [0,0] 和 [1,1] 不能移除因为它们没有与另一块石头同行/列。示例 3输入stones [[0,0]]输出0解释[0,0] 是平面上唯一一块石头所以不可以移除它。题解class Solution { private: unordered_mapint, int parent; int count 0; // 查找根节点带路径压缩 int find(int x) { if (parent.find(x) parent.end()) { parent[x] x; count; } if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; } // 合并两个节点 void unite(int x, int y) { int rx find(x), ry find(y); if (rx ! ry) { parent[rx] ry; count--; } } public: int removeStones(vectorvectorint stones) { parent.clear(); count 0; const int OFFSET 10001; // 区分行与列 for (auto s : stones) { unite(s[0] OFFSET, s[1]); } return stones.size() - count; } };// 并查集特殊模板2 class UnionFind{ // 本题因为是按行列进行查找优化可以直接采用哈希表 public: // 哈希表映射关系[key,parent] unordered_mapint,int parent; // 总共有多少不连通的并查集 int count 0; // 并查集查找首领节点操作 int Find(int index){ // 一开始构建并查集时候假如key值不在并查集中则构建哈希表映射count if(parent.find(index) parent.end()){ parent[index] index; count; } // 查找并查集的首领节点并优化 if(parent[index] ! index) parent[index] Find(parent[index]); return parent[index]; } // 并查集合并操作 void Uniod(int index1,int index2){ int parent1 Find(index1); int parent2 Find(index2); // *这步骤很重要直接把两节点首领一样的结果返回过滤否则会让count多减1* if(parent1 parent2) return; parent[parent1] parent2; count--; } }; class Solution { public: // 思路将石头行列的数值构建并查集因此行或列需要加10001区分开 // 合并的意思所有横坐标为 x 的石头和所有纵坐标为 y 的石头都属于同一个并查集 // 最后返回石头数量 - 并查集的数量就是题目要求的最多 int removeStones(vectorvectorint stones) { UnionFind uf; for(auto stone:stones){ uf.Uniod(stone[0] 10001,stone[1]); } return stones.size() - uf.count; } };