图 1：本文封面，点明「合并成互不重叠分组」的目标。
先说明属性：这是一篇历史题目复盘，题目出自本地历史面试资料，与任何公司的当前招聘无关。题面只有一句话：给若干集合，只要两个集合有公共元素就合并，最终输出若干互不重叠的集合。
先把问题翻译对。暴力做法是反复两两比较、见到交集就合并，直到不再变化——集合一多就是平方甚至立方级的开销。面试官真正想听的是你把它抽象成图问题的那一步：**元素是点，「同在一个集合」是边，答案就是这张图的连通分量。**而找连通分量的轻量标配，是并查集。
核心结论：用并查集，遍历一遍输入集合，把同集合的元素两两 union，最后按根分组，近线性时间收工。
并查集就两个操作。
初始时每个元素自成一个集合，父指针指向自己。find(x)：沿父指针一路找到根，根代表这个元素所在的组——两个元素根相同，就是同组。union(x, y)：先各找根，根不同就把一个根挂到另一个根下，两组合二为一。口诀九个字：查根判同组，挂根并两组。
两个优化让它快到接近常数。
朴素并查集的树可能退化成一条长链，find 一次要走 O(n)。两个优化专治这个：路径压缩——find 时把沿途节点直接挂到根上，树越查越扁；按秩合并——union 时让矮树挂到高树下面，树高长得慢。两个一起上，单次操作的均摊复杂度是 O(α(n))，α 是反阿克曼函数，在宇宙尺度的 n 下也不超过 5，工程上就当常数。
拿题面走一遍。
输入四个集合 {1,2,3}、{3,4}、{5,6}、{6,7}。处理第一个集合：union(1,2)、union(1,3)，1、2、3 同根。第二个集合含 3 和 4：union(3,4) 把 4 挂进同一棵大树——这就是「有交集则合并」的落地，交集元素 3 是两座集合之间的桥。同理后两个集合经 6 桥接成 {5,6,7}。最后对所有元素做 find 按根分组，输出 {1,2,3,4} 与 {5,6,7}。
写出可运行的代码。
下面实现带路径压缩与按秩合并的并查集，先跑上面的示例，再用随机用例与 BFS 求连通分量的结果对拍。用 Node.js 22.15.0 直接运行（node union-find.js）即可：
'use strict';
class UnionFind {
constructor() {
this.parent = new Map(); // 元素 -> 父元素
this.rank = new Map(); // 根 -> 树高上界
}
find(x) {
if (!this.parent.has(x)) { this.parent.set(x, x); this.rank.set(x, 0); }
let root = x;
while (this.parent.get(root) !== root) root = this.parent.get(root);
// 路径压缩：沿途节点直接挂到根上
while (this.parent.get(x) !== root) {
const next = this.parent.get(x);
this.parent.set(x, root);
x = next;
}
return root;
}
union(a, b) {
let ra = this.find(a), rb = this.find(b);
if (ra === rb) return;
if (this.rank.get(ra) < this.rank.get(rb)) [ra, rb] = [rb, ra]; // 按秩合并
this.parent.set(rb, ra);
if (this.rank.get(ra) === this.rank.get(rb)) this.rank.set(ra, this.rank.get(ra) + 1);
}
groups() {
const byRoot = new Map();
for (const x of this.parent.keys()) {
const r = this.find(x);
if (!byRoot.has(r)) byRoot.set(r, []);
byRoot.get(r).push(x);
}
return [...byRoot.values()].map((g) => g.sort((p, q) => p - q));
}
}
function mergeSets(sets) {
const uf = new UnionFind();
for (const s of sets) for (let i = 1; i < s.length; i++) uf.union(s[0], s[i]);
return uf.groups();
}
// 示例：{1,2,3}、{3,4}、{5,6}、{6,7}
const demo = [[1, 2, 3], [3, 4], [5, 6], [6, 7]];
console.log('示例合并结果：', JSON.stringify(mergeSets(demo)));
// 对拍基准：建图后用 BFS 求连通分量
function bfsGroups(sets) {
const adj = new Map();
const link = (a, b) => {
if (!adj.has(a)) adj.set(a, []);
adj.get(a).push(b);
};
for (const s of sets) for (let i = 1; i < s.length; i++) { link(s[0], s[i]); link(s[i], s[0]); }
const seen = new Set(), out = [];
for (const start of adj.keys()) {
if (seen.has(start)) continue;
const q = [start], g = [];
seen.add(start);
while (q.length) {
const cur = q.shift();
g.push(cur);
for (const nb of adj.get(cur)) if (!seen.has(nb)) { seen.add(nb); q.push(nb); }
}
out.push(g.sort((p, q) => p - q));
}
return out;
}
const key = (gs) => JSON.stringify(gs.map((g) => g.join('-')).sort());
let bad = 0;
for (let t = 0; t < 2000; t++) {
const sets = [];
for (let k = 0; k < 6; k++) {
const size = 1 + Math.floor(Math.random() * 4);
const s = new Set();
while (s.size < size) s.add(1 + Math.floor(Math.random() * 20));
sets.push([...s]);
}
if (key(mergeSets(sets)) !== key(bfsGroups(sets))) bad++;
}
console.log('2000 组随机对拍（基准为 BFS 连通分量），不一致组数：', bad);
实测输出：
示例合并结果： [[1,2,3,4],[5,6,7]]
2000 组随机对拍（基准为 BFS 连通分量），不一致组数： 0
图 2：find 与 union 的机制、两个优化与适用清单。
可能的追问。
「元素不是整数而是字符串 ID 怎么办？」示例代码用的就是哈希表而不是数组，天然支持任意可哈希元素。「要支持删除一个元素呢？」这是并查集的短板——合并容易拆分难，真要拆只能重建或换动态连通性数据结构。「和 BFS 找连通分量比，优势在哪？」边是「流式到达」时，并查集每来一条边 O(α(n)) 就地合并，还能随时回答「这两个元素同组吗」；BFS 适合图已静态成型、一次性算全量的场景。
易错点清单。
一，find 不做路径压缩、union 不看秩，被追问复杂度时只能说「应该挺快」。二，union 之前不判同根，把秩加错。三，输出分组时忘了根相同的才算一组，直接按输入顺序切段。四，只背得出结构，讲不出「元素是点、同集合是边、答案是连通分量」这层抽象——这层翻译才是题目的考点。
这道题的影子在工程里到处都是：实体对齐把多个来源的同一个人并成一档，账号关联把手机号、邮箱、设备号串成同一用户，语料近重复聚类把相似文档归成一簇。下次遇到「把有关系的东西归堆」，先想想并查集。
你在真实业务里用过并查集吗？是解决账号关联、实体对齐，还是别的归堆问题？欢迎分享。