title
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
solution
并查集问题，给一组(x,y)坐标，如果两点x或y相等，则相连，这里要x与y相连，变成一维问题。
class Solution:
def removeStones(self, stones: List[List[int]]) -> int:
uf = {}
def find(x):
if uf[x] != x:
uf[x] = find(uf[x])
return uf[x]
def union(a, b):
uf.setdefault(a, a)
uf.setdefault(b, b)
uf[find(a)] = find(b)
for i, j in stones:
union(i, 10000 + j)
return len(stones) - len({find(x) for x in uf})