给出一些坐标，每个坐标上有一枚石子，如果某个石子存在同行或同列的石子，那么可以去掉这颗石子，问最多可以去掉多少颗
符合同行or同列的石子集合组成一个连通分量，每个连通分量可以只留下一颗石子（沿着DFS路径一路去掉石子）
方法一：DFS求连通分量个数
1 #947
2 #Runtime: 1060 ms
3 #Memory Usage: 14.5 MB
4
5 class Solution(object):
6 def DFS(self, r, c):
7 if len(self.dict_stones_row[r]) > 1:
8 for j in self.dict_stones_row[r]:
9 if [r, j] not in self.vis:
10 self.vis.append([r, j])
11 self.DFS(r, j)
12 if len(self.dict_stones_col[c]) > 1:
13 for j in self.dict_stones_col[c]:
14 if [j, c] not in self.vis:
15 self.vis.append([j, c])
16 self.DFS(j, c)
17 return
18
19 def removeStones(self, stones):
20 """
21 :type stones: List[List[int]]
22 :rtype: int
23 """
24 self.dict_stones_row = {}
25 self.dict_stones_col = {}
26 self.vis = []
27 for i in stones:
28 if i[0] not in self.dict_stones_row:
29 self.dict_stones_row[i[0]] = []
30 self.dict_stones_row[i[0]].append(i[1])
31 if i[1] not in self.dict_stones_col:
32 self.dict_stones_col[i[1]] = []
33 self.dict_stones_col[i[1]].append(i[0])
34 nc = 0
35 for i in stones:
36 if i not in self.vis:
37 self.DFS(i[0], i[1])
38 nc += 1
39 return len(stones) - nc
方法二：并查集，是DFS的几乎8倍速度，看Discussion获得的思路，小技巧是可以将纵坐标i用~i操作转化为和横坐标无overlap的值，这样可以塞进一个并查集统一处理这个并查集写法也很简洁
1 #947
2 #Runtime: 129 ms
3 #Memory Usage: 14.1 MB
4
5 class Solution(object):
6 def find(self, x):
7 if x != self.uf.setdefault(x, x):
8 self.uf[x] = self.find(self.uf[x])
9 return self.uf[x]
10
11 def removeStones(self, stones):
12 """
13 :type stones: List[List[int]]
14 :rtype: int
15 """
16 self.uf = {}
17 for i, j in stones:
18 self.uf[self.find(i)] = self.find(~j)
19 return len(stones) - len({self.find(x) for x in self.uf})