描述:二维平面中有 n 块石头,每块石头都在整数坐标点上,且每个坐标点上最多只能有一块石头。如果一块石头的同行或者同列上有其他石头存在,那么就可以移除这块石头。

要求:返回可以移除的石子的最大数量。

不会有两块石头放在同一个坐标点上。

解释:一种移除 5 块石头的方法如下所示:

题目“求最多可以移走的石头数目”也可以换一种思路:“求最少留下的石头数目”。

如果两个石头 A、B 处于同一行或者同一列,我们就可以删除石头 A 或 B,最少留下 1 个石头。

如果三个石头 A、B、C,其中 A、B 处于同一行,B、C 处于同一列,则我们可以先删除石头 A,再删除石头 C,最少留下 1 个石头。

如果有 n 个石头,其中每个石头都有一个同行或者同列的石头,则我们可以将 n - 1 个石头都删除,最少留下 1 个石头。

通过上面的分析,我们可以利用并查集,将同行、同列的石头都加入到一个集合中。这样“最少可以留下的石头”就是并查集中集合的个数。

则答案为:最多可以移走的石头数目 = 所有石头个数 - 最少可以留下的石头(并查集的集合个数)。

最后计算集合个数,可以使用 set 集合去重,然后统计数量。

整体步骤如下:

遍历每块石头的横纵坐标:

然后将当前石头的横纵坐标相连接(加入到并查集中)。

建立一个 set 集合,查找每块石头横坐标所在集合对应的并查集编号,将编号加入到 set 集合中。