题目链接：https://leetcode-cn.com/problems/most-stones-removed-with-same-row-or-column/
题目
n 块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。
如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头。
给你一个长度为 n 的数组 stones ，其中 stones[i] = [xi, yi] 表示第 i 块石头的位置，返回 可以移除的石子 的最大数量。
示例1
- 输入： stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
- 输出： 5
- 解释： 一种移除 5 块石头的方法如下所示：
- 移除石头 [2,2] ，因为它和 [2,1] 同行。
- 移除石头 [2,1] ，因为它和 [0,1] 同列。
- 移除石头 [1,2] ，因为它和 [1,0] 同行。
- 移除石头 [1,0] ，因为它和 [0,0] 同列。
- 移除石头 [0,1] ，因为它和 [0,0] 同行。 石头 [0,0] 不能移除，因为它没有与另一块石头同行/列。
分析
其实不知道这题该算错题还是难题，毕竟它的思路是简单的，但是我并没有想到。
暂且归为错题罢。借由此题捡回了并查集的相关知识，在实现并查集的过程中有一些细节上的错误导致了一次WA，本篇将加以记录。
分析：
由题意可知，在同一行或同一列上的石头属于同一个集合。显然，这样的集合永远可以找到一个删除的顺序，使得集合中只剩下唯一一个石头。
于是题目转化为了以行列为依据的并查集问题。对于一块石头
idx，其坐标为(x, y)，如果x行上已经有了先来的石头root_x[x]，那么将idx加入先前就存在的root_x[x]的并查集中；否则表示idx是这一行最先到达的石头，其后的所有石头都要加入idx的并查集中。对于y列来说同理。于是实现并查集如下：
int parent[1010]; // 并查集 // memset(parent, -1, sizeof(parent)); // 或者 // for (i = 0; i < 1010; i++) parent[i] = i; void join(int parent_idx, int son_idx) { int root_p = find(parent_idx); int root_s = find(son_idx); if (root_p == root_s) return; else parent[root_s] = root_p; } int find(int idx) { if (parent[idx] == -1) return idx; parent[idx] = find(parent[idx]); // 路径压缩 return parent[idx]; }我们遍历所有石头，谁先到达某一行，之后这一行上的石头都要作为它的子节点；谁先到达某一列，之后这一列上的石头都要作为它的子节点。
这一轮遍历之后，所有同行同列的石头都处于同一个并查集中；而全局中并查集的个数就是剩余的石头个数。
class Solution { public: int parent[1010]; // 并查集 int root_x[10010]; int root_y[10010]; void join(int parent_idx, int son_idx) { int root_p = find(parent_idx); int root_s = find(son_idx); if (root_p == root_s) return; else parent[root_s] = root_p; } int find(int idx) { if (parent[idx] == -1) return idx; parent[idx] = find(parent[idx]); // 路径压缩 return parent[idx]; } int removeStones(vector<vector<int>>& stones) { int idx, x, y; memset(parent, -1, sizeof(parent)); memset(root_x, -1, sizeof(root_x)); memset(root_y, -1, sizeof(root_y)); for (idx = 0; idx < stones.size(); ++idx) { x = stones[idx][0]; y = stones[idx][1]; if (root_x[x] == -1) { root_x[x] = idx; } else { join(root_x[x], idx); } if (root_y[y] == -1) { root_y[y] = idx; } else { join(root_y[y], idx); } } int cnt = 0; for (idx = 0; idx < stones.size(); ++idx) { if (find(idx) == idx) { ++cnt; cout << idx << " "; } } return stones.size() - cnt; } };
错误记录
并查集中的
join函数，原本的写法为：void join(int parent_idx, int son_idx) { parent[son_idx] = parent_idx; }这样的写法是错误的，且非常之离谱。我们知道，两个属于不同并查集的元素的合并意味着两个并查集的合并，显然不能单纯地修改这两个元素本身，而要考虑到这两个并查集的根节点。
就本题来说，这样的写法无法通过这个测试样例：
[[0,1],[1,0],[1,1]]对于最后一块石头
(1, 1)，第1行已经有了石头1，第1列已经有了石头0。按照遍历过程的逻辑：for (idx = 0; idx < stones.size(); ++idx) { x = stones[idx][0]; y = stones[idx][1]; if (root_x[x] == -1) { root_x[x] = idx; } else { join(root_x[x], idx); } if (root_y[y] == -1) { root_y[y] = idx; } else { join(root_y[y], idx); } }最后一块石头最终将加入
0号并查集。且此时剩余独立的并查集有0和1。然而，最后一块石头实际上是
0和1的交汇点。按照正确的流程，它根据x坐标首先加入1号并查集后，再加入0号并查集，这时就会将1号石头也带入0号并查集，这也是本题使用并查集思路的正确性所在。正确的办法是在合并时考虑根节点的修改，详见前文代码。
此外，本题使用的并查集还可以进行优化，包括针对本题的封装（参考[1]），和针对并查集这一结构本身的按秩合并和路径压缩（参考[2]）。
本题还有基于图论的解法，不在本篇讨论范围内。
参考资料
[1] 小宇.简单思路+优化（超100%）[EB/OL].2021-01-15
[2] yex.【详解】并查集[EB/OL].2021-01-15
