1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
# 947. Most Stones Removed with Same Row or Column
"""
on a 2d plane, we place 'n' stones at some integer coordinate stones. each
coordinate point may have at most one stone. a stone can be removed if it
shares either the same row or the same column as another stone that has not
been removed. given an array 'stones' of length 'n' where 'stones[i] = [x_i,
y_i]' represents the location of the i'th stone, return the largest possible
number of stones that can be removed
"""
class Solution(object):
def removeStones(self, stones):
"""
:type stones: List[List[int]]
:rtype: int
"""
uf = {}
def find(x):
if x != uf.setdefault(x, x):
uf[x] = find(uf[x])
return uf[x]
for i, j in stones:
uf[find(i)] = find(~j)
return len(stones) - len({find(x) for x in uf})
if __name__ == "__main__":
obj = Solution()
print(obj.removeStones(stones=[[0, 0], [0, 1], [1, 0], [1, 2], [2, 1], [2, 2]]))
print(obj.removeStones(stones=[[0, 0], [0, 2], [1, 1], [2, 0], [2, 2]]))
|