給出一些坐標(biāo)，每個(gè)坐標(biāo)上有一枚石子，如果某個(gè)石子存在同行或同列的石子，那么可以去掉這顆石子，問最多可以去掉多少顆
符合同行or同列的石子集合組成一個(gè)連通分量，每個(gè)連通分量可以只留下一顆石子（沿著DFS路徑一路去掉石子）
方法一：DFS求連通分量個(gè)數(shù)
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獲得的思路，小技巧是可以將縱坐標(biāo)i用~i操作轉(zhuǎn)化為和橫坐標(biāo)無overlap的值，這樣可以塞進(jìn)一個(gè)并查集統(tǒng)一處理這個(gè)并查集寫法也很簡潔
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})