LeetCode-947. Most Stones Removed with Same Row or Column

LeetCode-947. Most Stones Removed with Same Row or Column

On a 2D plane, we place stones at some integer coordinate points.  Each coordinate point may have at most one stone.

Now, a move consists of removing a stone that shares a column or row with another stone on the grid.

What is the largest possible number of moves we can make?

Example 1:

Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]Output: 5

Example 2:

Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]Output: 3

Example 3:

Input: stones = [[0,0]]Output: 0

Note:

​​1 <= stones.length <= 1000​​​​0 <= stones[i][j] < 10000​​

题解：

使用并查集，寻找图中连通分量的个数，最后的结果就是石子的个数减去连通分量的个数。

前10000个数对应x，后10000个数对应y，减少搜索数。

class Solution {public: int f(int x, vector &root) { if (root[x] != x) { return f(root[x], root); } else { return x; } } void u(int x, int y, vector &root) { int rx = f(x, root); int ry = f(y, root); if (rx != ry) { root[ry] = rx; } } int removeStones(vector>& stones) { int n = stones.size(); vector root(20000, 0); unordered_set s; for (int i = 0; i < 20000; i++) { root[i] = i; } for (int i = 0; i < n; i++) { u(stones[i][0], stones[i][1] + 10000, root); } for (int i = 0; i < n; i++) { s.insert(f(stones[i][0], root)); } return n - s.size(); }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。