题目描述
思路解析动画文字版
记住「行列当节点 → 每颗石头 union 它的行和列 → 答案 = 石头数 − 连通块数」,下面逐帧套它。
先为用到的行、列各放一个节点:上排是第 0、1、2 行(R0、R1、R2),下排是第 0、1、2 列(C0、C1、C2)。此刻它们彼此独立,连通块数 = 6,相当于行列还没被任何石头牵连。
并查集准备就绪:每个行/列节点的 parent 先指向自己。接下来按顺序扫每颗石头,把它的行节点和列节点并起来。
第 1 颗石头 (0, 0):它占住第 0 行和第 0 列,所以要把行节点 R0 和列节点 C0 连起来(它俩高亮)。
union(R0, C0):各自 find 出根后,把 R0 那组的根接到 C0 所在组的根上(union 永远是接到对方的根、不是接到某个普通节点),两组并成同一个连通块(同色)。连通块数减 1,现在是 5。
第 2 颗石头 (0, 1):它占住第 0 行和第 1 列,所以要把行节点 R0 和列节点 C1 连起来(它俩高亮)。
union(R0, C1):各自 find 出根后,把 R0 那组的根接到 C1 所在组的根上(union 永远是接到对方的根、不是接到某个普通节点),两组并成同一个连通块(同色)。连通块数减 1,现在是 4。
第 3 颗石头 (1, 0):它占住第 1 行和第 0 列,所以要把行节点 R1 和列节点 C0 连起来(它俩高亮)。
union(R1, C0):各自 find 出根后,把 R1 那组的根接到 C0 所在组的根上(union 永远是接到对方的根、不是接到某个普通节点),两组并成同一个连通块(同色)。连通块数减 1,现在是 3。
第 4 颗石头 (1, 2):它占住第 1 行和第 2 列,所以要把行节点 R1 和列节点 C2 连起来(它俩高亮)。
union(R1, C2):各自 find 出根后,把 R1 那组的根接到 C2 所在组的根上(union 永远是接到对方的根、不是接到某个普通节点),两组并成同一个连通块(同色)。连通块数减 1,现在是 2。
第 5 颗石头 (2, 1):它占住第 2 行和第 1 列,所以要把行节点 R2 和列节点 C1 连起来(它俩高亮)。
union(R2, C1):各自 find 出根后,把 R2 那组的根接到 C1 所在组的根上(union 永远是接到对方的根、不是接到某个普通节点),两组并成同一个连通块(同色)。连通块数减 1,现在是 1。
第 6 颗石头 (2, 2):它占住第 2 行和第 2 列,所以要把行节点 R2 和列节点 C2 连起来(它俩高亮)。
union(R2, C2):先各自 find 根,发现 R2 和 C2 已经在同一个连通块里了(被前面的石头经别的行列间接连通过)。这一步是个环、不改变结构,连通块数仍是 1。
六颗石头都扫完了。看整张图:R0、R1、R2、C0、C1、C2 六个行列节点经一连串 union 全连到了一起,只剩 1 个连通块,说明这 6 颗石头其实是「互相牵连」的一大堆。
数连通块的办法:对每个节点做一次 find 拿到它的根,根相同的就是同一块。下面逐个看,看它们是不是都指向同一个根。
find(R0) 的根是 C2。这是目前见到的第 1 个不同的根。
find(R1) 的根是 C2。和前面某个节点的根相同,归入同一连通块,不新增。
find(R2) 的根是 C2。和前面某个节点的根相同,归入同一连通块,不新增。
find(C0) 的根是 C2。和前面某个节点的根相同,归入同一连通块,不新增。
find(C1) 的根是 C2。和前面某个节点的根相同,归入同一连通块,不新增。
find(C2) 的根是 C2。和前面某个节点的根相同,归入同一连通块,不新增。
数下来只有 1 个不同的根,也就是 1 个连通块。每个连通块里的石头互相同行或同列连着,可以一颗颗移到只剩 1 颗。所以最多移除 = 石头数 − 连通块数 = 6 − 1 = 5。
边界:全分散移 0;全连通移 n−1;单石移 0。
两个追问:每块可移到剩 1 颗;DFS/BFS 求连通分量等价。
参考代码
from typing import Listclass Solution: def removeStones(self, stones: List[List[int]]) -> int: parent = {} def find(x): parent.setdefault(x, x) if parent[x] != x: parent[x] = find(parent[x]) return parent[x] for r, c in stones: parent[find(('r', r))] = find(('c', c)) roots = {find(('r', r)) for r, _ in stones} return len(stones) - len(roots)复杂度
- 时间：近似 O(n)，n 是石头数。每颗石头做一次 union(两次 find);本实现只用了路径压缩(没有按秩合并),单次操作均摊也已接近常数;统计根再扫一遍 n,合计近似线性
- 空间：O(n)，parent 哈希表最多存 2n 个行列节点(每颗石头一行一列),量级 O(n)
易错点
面试追问把动画讲成自己的话
追问为什么每个连通块一定能移到只剩 1 颗?
追问能不能不用并查集,改用 DFS/BFS 求连通分量?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
等式方程的可满足性
LeetCode 990 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题