947. Most Stones Removed with Same Row or Column
## 思路
stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
分成兩個group:
[0,0], [0,2], [2,0], [2,2] -> 刪掉3個stone
[1,1]
用兩個dict 記錄每個row跟col最後看到的石頭idx
如果在同一條線上已經有石頭了, 就作union find
## Code
```python
class UnionFind:
def __init__(self, n):
self.root = list(range(n))
self.rank = [1] * n
def find(self, x):
if self.root[x] != x:
self.root[x] = self.find(self.root[x])
return self.root[x]
def union(self, x, y):
rx, ry = self.find(x), self.find(y)
if rx == ry:
return 0
if self.rank[rx] >= self.rank[ry]:
self.rank[rx] += self.rank[ry]
self.root[ry] = rx
else:
self.rank[ry] += self.rank[rx]
self.root[rx] = ry
return 1
class Solution:
def removeStones(self, stones: List[List[int]]) -> int:
n = len(stones)
uf = UnionFind(n)
seen_rows = defaultdict(int) # row -> idx
seen_cols = defaultdict(int) # col -> idx
res = 0
for idx, (r, c) in enumerate(stones):
if r in seen_rows:
res += uf.union(seen_rows[r], idx)
if c in seen_cols:
res += uf.union(seen_cols[c], idx)
seen_rows[r] = idx
seen_cols[c] = idx
return res
```