先还原一次线上工单。一位用户用手机号注册了主账号,后来又用两个邮箱注册了两个副账号,三个账号都领过券。客服在后台点下「合并」之后,页面显示只合并了两个,第三个还在,券也留在第三个账号里。用户找不到券,工单从客服升到研发。
排查发现,合并表里存的是「谁并进了谁」:账号 A 并进 B,B 又并进 C。读取的时候只往上看了一层,A 看得到 B,却看不到 B 上面还有 C。修法有两种:要么在每个读取路径上都写一遍「一直往上找到底」,要么让每个账号只记住一个最终归属,谁来问都直接给出答案。
同一个项目里还有另一件事。每天跑的「疑似同人」检测,把二十万个账号两两比对邮箱和手机号,算下来接近两百亿次比较,跑一夜也出不来结果。一个是不对,一个是不快,根子却是同一个:程序在反复回答「这两个账号是不是同一个集合」,而每一次都在用最笨的方法现算。
这篇要讲的并查集(union-find,也叫不相交集合),就是专门回答这个问题的一种结构。它不存关系图,不存路径,只存「谁和谁是一伙的」。
账号合并真正难在哪
先把问题说准。并查集解决的是「动态连通性」:有一堆元素,不断有「这两个属于同一个集合」的消息进来,同时随时要问「这两个现在在不在同一个集合」。它只回答是或否,不告诉你集合里有哪些人,也不告诉你两个人之间隔了几条关系。集合内部长什么样,它完全不关心。
这里的「同一个集合」要满足三条性质:自己和自己算同一个,这叫自反;A 和 B 同集合,B 和 A 也同集合,这叫对称;A 和 B 同集合、B 和 C 同集合,那么 A 和 C 也同集合,这叫传递。第三条最关键,也是开头那次事故的来源。合并必须能一路传下去,不能只记一层。
并查集对外只做两件事。第一件是 find,问某个元素的根是谁;第二件是 union,把两个元素所在的集合并成一个。工程上的用法很直接:把每条线索当成一次 union,最后数一数还剩几个根,就知道分成了几组。
注意这个流程里没有「遍历所有账号」。合并一条线索的代价,只和这次 find 走多深有关,和总人数几乎无关。这正是它比「每次两两比对」强的地方。
parent 数组与 find:集合只认根
并查集最朴素的实现只有一个数组,叫 parent。parent[i] 记的是 i 的父节点是谁。如果一个元素的父节点就是它自己,它就是这棵树的根(root)。每个集合是一棵树,树的根是这个集合的唯一代表,也可以理解成集合的名字。
find 的逻辑短到可以背下来:父节点不是自己就继续走,父节点是自己就停。判断两个元素是否同集合,只要比较 find(a) 和 find(b) 的返回值是不是同一个编号。这里比较的是根,不是元素本身,也不是父节点。
const parent = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
parent[1] = 0;
parent[2] = 0;
parent[3] = 2;
function find(x) {
while (parent[x] !== x) x = parent[x];
return x;
}
console.log(find(3), find(2), find(3));
本机输出是 0 0 0。3 上面挂了两层:3 的父节点是 2,2 的父节点是 0,0 是自己的父节点。find(3) 走两步到 0;find(2) 走一步到 0;再调用一次 find(3) 还是 0,因为树的结构没有变,每次都要重新走那两步。
初始化时每个元素自成一个集合,parent[i] 都等于 i,所以有 n 个根,也就是 n 个集合。这一步是 O(n),只做一次。之后所有操作都在这套父子关系上改,不再新建数组。
union:把根挂到根下面
union(a, b) 做的事分三步:先找到 a 的根,再找到 b 的根;两个根相同,说明已经同集合,什么都不做,返回 false;两个根不同,就把其中一棵树的根挂到另一棵树的根下面,返回 true。挂接只改一个 parent 值,所以 union 本身的动作很便宜,成本几乎都花在两次 find 上。
下面这版是完整的类,带按秩合并(合并时让矮树挂到高树下面)、路径压缩(查询后把路上的点直接挂到根)和实时维护的集合个数。先看用法,原理在后面两节拆。
class UnionFind {
constructor(n) {
this.parent = Array.from({ length: n }, (_, i) => i);
this.rank = new Array(n).fill(0);
this.count = n;
}
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]);
}
return this.parent[x];
}
union(a, b) {
let ra = this.find(a), rb = this.find(b);
if (ra === rb) return false;
if (this.rank[ra] < this.rank[rb]) [ra, rb] = [rb, ra];
this.parent[rb] = ra;
if (this.rank[ra] === this.rank[rb]) this.rank[ra]++;
this.count--;
return true;
}
}
本机跑了一组十个元素的用例:依次执行 union(0, 1)、(2, 3)、(1, 2)、(4, 5)、(6, 7),五次都返回 true,说明每次合并的两个元素原本确实不连通。随后 find(0) 到 find(9) 依次得到 0,0,0,0,4,4,6,6,8,9,能看出三个多元素集合:根 0 里是 0 到 3,根 4 里是 4 和 5,根 6 里是 6 和 7,另外 8 和 9 各自独立。再执行 union(0, 3),返回 false,因为 0 和 3 早就在根 0 下面了。此时 count 是 5,表示还剩五个集合。
union 的返回值不是装饰。Kruskal 算法就是靠它判断一条边要不要收进最小生成树:返回 true 说明这条边连接了两个还没通的块,收下;返回 false 说明两端早就连通,加了会成环,丢掉。这个小布尔值把「判环」和「合并」合并成了一次操作。
别让树长歪:按秩与按大小
如果 union 永远把第二棵树的根挂到第一棵下面,树会越长越歪。设想每次都把一棵大树挂到一个刚出现的单节点下面,树就退化成一条链,find 从最底下走到根要一万步。数据量一大,原本以为很快的操作就变成了线性。
按秩合并(union by rank)的做法是:每个根记一个 rank,表示这棵树高度的上界。合并时把 rank 小的根挂到 rank 大的根下面;两个 rank 相同,就随便挂一个,再给新根加一。这样任何一棵树的深度都不会超过 log n。本机构造一万个节点、每次都把大树挂到新节点下面:不按秩时最大深度是 9999,按秩时最大深度是 1。
按秩合并
每个根多存一个 rank,只看高度,不数人数。合并时 rank 小的挂到 rank 大的下面,相等则任意挂并加一。实现省一个维护步骤,适合大多数场景。
按大小合并
每个根多存一个 size,记录集合里有多少元素。合并时把小的挂到大的下面,并把 size 相加。它和按秩效果几乎一样,路径压缩后维护 size 更直观。
两者选一个就行,不用同时维护。它们都是启发式,不改变正确性,只改变树的形状。不加也不会算错,只是最坏情况下会慢;加了之后,树高被压在对数级别,find 的步数就有了保证。rank 只是「上界」,路径压缩会把实际形状改平,所以别拿 rank 当真实高度去用。
路径压缩:走一次就把路修平
路径压缩解决的是另一种浪费:find 每次从下往上走,走完就把整条路扔掉了,下次同样的查询还要再走一遍。它的做法很直接:既然这次已经走到了根,那就把路上经过的每个节点都直接挂到根上,下次一步就到。集合的归属没有变,变的只是记录的层级。
function makeChain(n) {
const p = Array.from({ length: n }, (_, i) => i);
for (let i = 0; i + 1 < n; i++) p[i] = i + 1;
return p;
}
function findCompressed(p, x) {
let root = x;
while (p[root] !== root) root = p[root];
while (x !== root) {
const next = p[x];
p[x] = root;
x = next;
}
return root;
}
本机拿一万个节点手工接成一条链:0 挂 1,1 挂 2,一直挂到 9999,根在末端。然后对每个节点各做一次 find。不压缩的版本一共走了 49995000 步父指针;压缩版本只走了 19997 步。差了大约两千五百倍。这不是玄学,就是把「每次重走长途」改成了「第一次走完就修路」。
递归写法也很常见,本文的类用的就是递归:parent[x] = find(parent[x]),一行顶三行。但如果数据是一条一万节点的长链,递归深度就可能把调用栈撑爆。工程里更稳妥的是上面这种两趟循环:第一趟找根,第二趟把一路上的节点挨个改指向根。两种写法结果一样,区别只在栈的消耗。
压缩之后树的结构被改平了,所以并查集的树高并不稳定,会随查询历史变化。这也解释了一个常见误解:按秩的 rank 不是「当前高度」,而是「曾经达到过的上界」,压缩之后它往往比真实高度大。
两个优化合起来到底多快
两个优化合起来,均摊时间是 O(α(n)),读作「阿尔法 n」。α 是反阿克曼函数(inverse Ackermann function),也就是阿克曼函数的反函数。它增长得极慢:就算 n 是宇宙里的原子数,大约十的八十次方,α(n) 也只是个位数。所以工程上可以当成常数用,但严格说它不是常数。
这句话里有两个词要理解。「均摊」是指单次操作偶尔会走很长,比如第一次 find 一条长链,但把成本摊到之后的所有查询上,平均下来很小。「上界」是指它描述最坏情况下的平均,不是某一次。别把「近似常数」理解成「任何一次都一瞬间」,第一次修路仍然要走路。
还有一个常被忽略的事实:只加路径压缩、不加按秩,均摊是 O(log n);只加按秩、不压缩,也是 O(log n);两个一起才是 O(α(n))。本机那组约五千万步的对照里,单加任意一个都能把总步数降到两万左右,所以小数据量下只做一半也够用;但数据量大、操作又多时,两边都写才是标准做法。
能拿它做什么
第一个用法是数连通分量。连通分量就是「互相能走到的点组成的一块」。初始 count 等于 n,每次成功 union 减一,最后 count 就是组数,不需要再遍历一遍父数组。账号合并、朋友圈、省份数量都是这个套路。本机用省份矩阵跑了两组:三个省份、前两个相连,返回 2;三个互不相连,返回 3。
第二个用法是 Kruskal 最小生成树。最小生成树是在连通图里选出一组边,把所有点连起来,并且总权重最小。做法是把边按权重从小到大排序,依次尝试;union 返回 true 就收下这条边,返回 false 就跳过。本机那组五节点七条边的图,选中的边是 (1,2,1)、(1,3,2)、(0,2,3)、(2,4,5),总权重 11。
第三个用法是判环。无向图里加一条边之前,先 union 两端;如果返回 false,说明两端早已连通,这条边会形成环。注意这只适用于无向图。有向图的环检测要看方向和拓扑顺序,不能直接套并查集,这是两种不同的问题。
function countProvinces(grid) {
const size = grid.length;
const set = new UnionFind(size);
for (let i = 0; i < size; i++)
for (let j = i + 1; j < size; j++)
if (grid[i][j] === 1) set.union(i, j);
return set.count;
}
console.log(countProvinces([[1,1,0],[1,1,0],[0,0,1]]));
console.log(countProvinces([[1,0,0],[0,1,0],[0,0,1]]));
function kruskal(size, edges) {
edges.sort((a, b) => a[2] - b[2]);
const set = new UnionFind(size);
let total = 0;
const picked = [];
for (const [u, v, w] of edges) {
if (set.union(u, v)) { total += w; picked.push([u, v, w]); }
}
return { total, picked };
}
const edges = [[0,1,4],[0,2,3],[1,2,1],[1,3,2],[2,3,4],[2,4,5],[3,4,6]];
const r = kruskal(5, edges);
console.log(r.total, JSON.stringify(r.picked));
输出依次是 2、3,以及 11 [[1,2,1],[1,3,2],[0,2,3],[2,4,5]]。Kruskal 的输出顺序跟着排序走,所以不是按边的原始顺序,而是按权重从小到大。
账号合并的具体做法也值得写清楚:把每个邮箱、每个手机号都映射成一个整数下标,同一个账号里的邮箱和手机号做一次 union。最后按根分组,同一组的账号就是同一个人的候选。这里要注意,并查集只给候选,不给证据;真要合并账号,还得有人工确认或更强的规则,否则同 IP、同设备这类弱标识会把陌生人并到一起。
现象、真实原因与第一步查什么
下面这些现象在写并查集、或者用并查集做业务时很常见。看到类似症状,先按表里的第一步定位,不要一上来就重写整个类。
| 现象 | 真实原因 | 第一步查什么 |
|---|---|---|
| 合并后仍有账号不在一起 | 合并记录只存了一层,读取时没有一路找到根 | 读取是否调用 find,而不是直接读 parent |
| 两个明显不同的人被合并 | 只按一个弱标识(同 IP、同设备)就 union | union 的触发条件是否足够强 |
| 合并任务越跑越慢 | find 没有路径压缩,长链被反复重走 | find 在返回前是否改写了路径 |
| 树退化成一条长链 | union 固定挂接,没有按秩或按大小 | union 是否比较 rank 或 size |
| 统计组数总是不对 | 把父节点个数当成集合个数,忽略了中间层 | 是否维护 count,或重新数「自己是根」的节点 |
| 用并查集判有向图环失败 | 并查集只处理无向连通性,不看方向 | 是否应该换拓扑排序 |
| 合并之后无法拆开 | 并查集不支持删除和分裂 | 业务是否需要撤销或拆分能力 |
| 递归 find 报栈溢出 | 压缩用了递归,正好遇到一条长链 | 是否改成两趟迭代写法 |
第一行和第五行是最常见的两种误用:一个把 parent 当成最终归属,忘了它可能只是中间人;一个把「父节点是自己」的节点数和集合数搞混。前者靠统一入口解决,所有查询都走 find;后者靠实时维护 count,或者老老实实数一遍根。
边界与代价
并查集的能力边界要说清楚。它只回答「同不同集合」,不回答「怎么连的」「隔了几步」「集合里都有谁」。想知道路径,要用图的遍历;想知道成员,得在每个根上挂一个列表,或者最后统一分组。它也不是图,不保存边,所以别指望从它里面还原出关系网。
它还不支持删除和拆分。union 之后两个集合就粘住了,没有现成的撤销操作。有些题用「可撤销并查集」,按栈序回滚合并,但那是额外技巧,不是基础能力。要支持删除,通常得换数据结构,或者把操作离线下来倒着做。
空间上,parent 和 rank 各一个长度为 n 的数组,是 O(n)。如果元素是字符串,比如邮箱、手机号,得先做一个映射表把它们编号,映射表本身也占空间。别直接拿字符串当下标,也别每次 find 都现场算哈希。
实现上还有几个坑:元素下标从 0 还是 1 开始要统一;输入里如果有不存在的编号,find 会越界;路径压缩会改写 parent,如果别处还依赖原始父子关系,就会读到被压平后的结构;并发场景下并查集不是线程安全的,多个线程同时 union 需要加锁或分片。
最后是常数代价。并查集的代码短,但每次 find 都有循环和赋值,路径压缩还会写字。它的优势建立在「操作次数多、每次只需要回答是或否」上;如果只查一两次,直接建图做一次遍历反而更清楚。别为了用而用。
当天能做的练习
- 把本文的 UnionFind 类原样敲进去,跑那组十个元素的用例,核对五个 true、find 序列 0,0,0,0,4,4,6,6,8,9、union(0,3) 返回 false 以及 count 为 5。
- 手工构造一万个节点的长链,分别用压缩和不压缩的 find 把所有节点查一遍,统计父指针步数,核对约五千万和约两万这两个量级。
- 把 UnionFind 的 rank 改成 size,实现按大小合并,重跑「每次都把大树挂到新节点」的实验,记录最大深度,再和按秩版本对比。
- 用并查集做省份数量,输入 [[1,1,0],[1,1,0],[0,0,1]] 和全零矩阵,确认输出 2 和 3;再把 count 改成最后重新数根,核对两种统计方式一致。
- 用并查集跑 Kruskal,把那七条边打乱顺序各跑三次,确认总权重始终是 11,并打印每次收下的边;再故意加一条会成环的边,观察 union 返回 false。
小结与组内回望
三句话收一下:并查集用 parent 数组把每个集合表示成一棵只认根的树,find 沿父指针走到根,union 把一根挂到另一根;按秩或按大小合并防止树长歪,路径压缩把查找路径上的点直接挂到根;两个优化合起来均摊 O(α(n)),工程上当成常数用。
组内回望:这一组前面几篇一直在和边打交道,怎么存边、怎么沿着边走、怎么按依赖顺序排点。上一篇拓扑排序解决的是「有向图里谁必须在谁前面」,它关心方向和先后;并查集解决的是「无向关系里谁和谁是一伙的」,它不关心方向,也不关心集合内部怎么连。一个排顺序,一个分团伙,拿到题先问自己:我要的是先后,还是同类。
这一组到此收尾,没有下一篇了。回头把这几篇的代码放在一起跑一遍,比只看结论更有用。