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
}
}