# 947. Most Stones Removed with Same Row or Column 移除最多的同行或同列石头

@TOC

## # 题目描述

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. 1 <= stones.length <= 1000
2. 0 <= stones[i][j] < 10000

## # 解题方法

### # 并查集

python代码如下，可惜超时了。

``````class Solution(object):
def removeStones(self, stones):
"""
:type stones: List[List[int]]
:rtype: int
"""
N = len(stones)
self.map = [-1] * N
for i in range(N):
for j in range(i + 1, N):
if stones[i][0] == stones[j][0] or stones[i][1] == stones[j][1]:
self.union(i, j)
res = N
print(self.map)
for i in range(N):
if self.map[i] == -1:
res -= 1
return res

def find(self, x):
return x if self.map[x] == -1 else self.find(self.map[x])

def union(self, x, y):
fx = self.find(x)
fy = self.find(y)
if fx != fy:
self.map[fx] = fy
``````

``````class Solution {
public:
int removeStones(vector<vector<int>>& stones) {
if(stones.size() <= 1) return 0;
int N = stones.size();
vector<int> p(N, -1);
for (int i = 0; i < N; ++i){
for(int j = i + 1; j < N; ++j){
if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]){
u(p, i, j);
}
}
}
int res = N;
for(auto e: p) if(e == -1) --res;
return res;
}
private:
int f(vector<int> &p, int x){
if(p[x] == -1) return x;
return f(p, p[x]);
}

void u(vector<int> &p, int x, int y){
int px = f(p, x);
int py = f(p, y);
if(px != py){
p[px] = py;
}
}
};
``````

Python代码如下：

``````class Solution(object):
def removeStones(self, stones):
"""
:type stones: List[List[int]]
:rtype: int
"""
N = len(stones)
self.map = [-1] * 20000
for x, y in stones:
self.union(x, y + 10000)
count = set()
return N - len({self.find(x) for x, y in stones})

def find(self, x):
return x if self.map[x] == -1 else self.find(self.map[x])

def union(self, x, y):
fx = self.find(x)
fy = self.find(y)
if fx != fy:
self.map[fx] = fy
``````

C++代码如下：

``````class Solution {
public:
int removeStones(vector<vector<int>>& stones) {
if(stones.size() <= 1) return 0;
int N = stones.size();
vector<int> p(20000, -1);
for(auto stone : stones){
u(p, stone[0], stone[1] + 10000);
}
set<int> parents;
for(auto stone : stones){
parents.insert(f(p, stone[0]));
}
return N - parents.size();
}
private:
int f(vector<int> &p, int x){
if(p[x] == -1) return x;
return f(p, p[x]);
}

void u(vector<int> &p, int x, int y){
int px = f(p, x);
int py = f(p, y);
if(px != py){
p[px] = py;
}
}
};
``````

## # 日期

2018 年 11 月 24 日 —— 周日开始！一周就过去了～