LeetCode 947. 移除最多的同行或同列石头（并查集）Michael是个半路程序员-

1. 题目

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

每次 move 操作都会移除一块所在行或者列上有其他石头存在的石头。

请你设计一个算法，计算最多能执行多少次 move 操作？

示例 1： 输入：stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]] 输出：5  示例 2： 输入：stones = [[0,0],[0,2],[1,1],[2,0],[2,2]] 输出：3  示例 3： 输入：stones = [[0,0]] 输出：0   提示： 1 <= stones.length <= 1000 0 <= stones[i][j] < 10000 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/most-stones-removed-with-same-row-or-column
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

参考 数据结构–并查集（Disjoint-Set）

• 把行号、列号看成一个单元
• 用并查集把每个点的行列merge
• 最后查找都有点有几个单元，点的个数减去单元个数就是能移走的石子

class dsu {     vector<int> f; public: dsu(int n) {         f.resize(n); for(int i = 0; i < n; ++i)             f[i] = i; } void merge(int a, int b) { int fa = find(a), fb = find(b);         f[fa] = fb; } int find(int a) { int origin = a; while(f[a] != a) {             a = f[a]; } return f[origin] = a; } }; class Solution { public: int removeStones(vector<vector<int>>& stones) {         dsu u(20000);         unordered_set<int> s; for(int i = 0; i < stones.size(); ++i)             u.merge(stones[i][0], stones[i][1]+10000); for(int i = 0; i < stones.size(); ++i)             s.insert(u.find(stones[i][0])); return stones.size()-s.size(); } }; 

60 ms 19.6 MB