947. Most Stones Removed with Same Row or Column
在一个2D平面上，放只了一些石头
同一个位置不会有2个以上的石头
如果在同一列/行上有石头，则可以把这颗石头移除掉
请回传最多可以移除几颗石头
思路：
将可以互相抵达的石头归类到同一个group
那么可移除的石头数量就是全部的石头数量-group数量
因为这题只给石头的座标，而不是整个平面的情况
所以用union find去将石头分类
首先先把石头之间的边建立起来
再来union find找出有几个group
就可以得到答案了
golang code :
func removeStones(stones [][]int) int {
edges, n := make([][]int, 0), len(stones)
row, col := make(map[int]int), make(map[int]int)
arr := make([]int, n)
cluster_chk := make([]bool, n)
for key, val := range stones {
arr[key] = key
if _, ok := row[val[0]]; !ok {
row[val[0]] = key
} else {
edges = append(edges, []int{row[val[0]], key})
}
if _, ok := col[val[1]]; !ok {
col[val[1]] = key
} else {
edges = append(edges, []int{col[val[1]], key})
}
}
for _, val := range edges {
union(arr, val[0], val[1])
}
for key := range stones {
arr[key] = find(arr, key)
}
numofcluster := 0
for _, val := range arr {
if !cluster_chk[val] {
numofcluster++
cluster_chk[val] = true
}
}
return n - numofcluster
}
func find(arr []int, idx int) int {
if arr[idx] == idx {
return idx
}
res := find(arr, arr[idx])
arr[idx] = res
return res
}
func union(arr []int, a, b int) {
parent_a := find(arr, a)
parent_b := find(arr, b)
if parent_a < parent_b {
arr[parent_b] = parent_a
arr[b] = parent_a
} else {
arr[parent_a] = parent_b
arr[a] = parent_b
}
}