947. 移除最多的同行或同列石头
947. 移除最多的同行或同列石头
难度中等182收藏分享切换为英文接收动态反馈
n 块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。
如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头。
给你一个长度为 n 的数组 stones ，其中 stones[i] = [xi, yi] 表示第 i 块石头的位置，返回 可以移除的石子 的最大数量。
示例 1：
输入：stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
输出：5
解释：一种移除 5 块石头的方法如下所示：
1. 移除石头 [2,2] ，因为它和 [2,1] 同行。
2. 移除石头 [2,1] ，因为它和 [0,1] 同列。
3. 移除石头 [1,2] ，因为它和 [1,0] 同行。
4. 移除石头 [1,0] ，因为它和 [0,0] 同列。
5. 移除石头 [0,1] ，因为它和 [0,0] 同行。
石头 [0,0] 不能移除，因为它没有与另一块石头同行/列。示例 2：
输入：stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
输出：3
解释：一种移除 3 块石头的方法如下所示：
1. 移除石头 [2,2] ，因为它和 [2,0] 同行。
2. 移除石头 [2,0] ，因为它和 [0,0] 同列。
3. 移除石头 [0,2] ，因为它和 [0,0] 同行。
石头 [0,0] 和 [1,1] 不能移除，因为它们没有与另一块石头同行/列。示例 3：
输入：stones = [[0,0]]
输出：0
解释：[0,0] 是平面上唯一一块石头，所以不可以移除它。提示：
1 <= stones.length <= 10000 <= xi, yi <= 10^4- 不会有两块石头放在同一个坐标点上
函数签名：
func removeStones(stones [][]int) int分析
在纸上画出这些石头，同行或同列的连线，这样就形成了一张图。
对于每一个联通分量，一定能在满足题目限制的条件下一一删除节点直到剩余一个节点，
具体删除顺序怎么找？见后边的拓展讨论。
基于上边的性质。每个联通分量最终剩余一个石头，用石头总数减去剩余的石头总数就是结果。
具体可以使用 dfs 或借助并查集来统计联通分量的个数。
DFS
func removeStones(stones [][]int) int {
n := len(stones)
graph := make([][]int, n)
for i := 0; i < n-1; i++ {
p := stones[i]
for j := i+1; j < n; j++ {
q := stones[j]
if p[0] == q[0] || p[1] == q[1] {
graph[i] = append(graph[i], j)
graph[j] = append(graph[j], i)
}
}
}
visited := make([]bool, n)
var dfs func(int)
dfs = func(v int) {
visited[v] = true
for _, w := range graph[v] {
if !visited[w] {
dfs(w)
}
}
}
cnt := 0
for i, v := range visited {
if !v {
cnt++
dfs(i)
}
}
return n - cnt
}并查集
func removeStones(stones [][]int) int {
n := len(stones)
uf := make([]int, n)
for i := range uf {
uf[i] = i
}
find := func(x int) int {
for x != uf[x] {
x, uf[x] = uf[x], uf[uf[x]]
}
return x
}
union := func(x, y int) {
rootX, rootY := find(x), find(y)
uf[rootX] = uf[rootY]
}
for i := 0; i < len(stones)-1; i++ {
si := stones[i]
for j := i+1; j < len(stones); j++ {
sj := stones[j]
if si[0] == sj[0] || si[1] == sj[1] {
union(i, j)
}
}
}
roots := 0
for i, v := range uf {
if i == v {
roots++
}
}
return n-roots
}时间复杂度 O(n^2)，主要是确定联通关系中的双重循环。
空间复杂度 O(1)。
拓展
1.具体删除顺序怎么找？
1.如果每个连通分量里没有环，将很容易证明：这时候就是一棵树，只需要从叶子节点 bfs 一一消除直到剩余一个节点；或者从任意一个根节点开始 dfs 后序遍历即可。
2.如果联通分量里有环，只需要把环内任意一条边打断，转化成1的情况。直接去找环并打断一条边的做法比较复杂，可以这样：将该联通分量的所有节点都看成散列的点，重新连边，只是在连边过程中看看要连的两个点是否已经联通（可以借助并查集），如果联通就不再连边。
2.考虑优化图模型
上边的解法建图效率较低，将石头看成图里的点，实际上可以直接将石头的行和列看成点。
直接将每个石子的行和列合并，可以理解为，每个点不是于其他点连接，而是连接到自身所在行与列上，所以可以用行与列的维度来合并。