200 万条社交关系里要反复判断”两个人是否属于同一个人脉圈”，挨个遍历肯定来不及——并查集（Union-Find）就是为这类动态连通性问题准备的。它只做两件事：查询两个元素是否同属一个集合（Find），以及把两个集合合并成一个（Union），配合路径压缩和按秩合并两项优化后，单次操作的均摊复杂度接近常数级。
用数组就能实现的树形结构
并查集的存储结构简单到只有一维数组：parent[i] 表示元素 i 的父节点。每个集合组织成一棵树，树的根节点就是这个集合的”代表元”——判断两个元素是否同属一个集合，等价于判断它们向上追溯到的根是否相同。
初始化时每个元素自成一个集合，父节点指向自己：
parent = list(range(n)) # parent[i] = i，各自为根
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # 路径压缩：跳过中间节点直连祖先
x = parent[x]
return x
def union(a, b):
ra, rb = find(a), find(b)
if ra == rb:
return False # 已在同一集合
parent[rb] = ra # 把一棵树挂到另一棵下面
return Truefind 里的 parent[x] = parent[parent[x]] 是路径压缩的精髓：每次查询顺路把链上的节点直接挂到祖父节点上，多次查询后整棵树会越来越扁，后续查询越来越快。这种写法叫”路径减半”，比递归版压缩更省栈空间。
没有优化会慢成什么样
只有数组的朴素并查集，极端情况下会退化成一条长链——所有元素首尾相接，find 一次要爬完整条链，复杂度退化到 O(n)。两项优化就是用来堵住这个漏洞的：
| 优化手段 | 做了什么 | 效果 |
|---|---|---|
| 路径压缩 | 查询时把沿途节点直接挂到根附近 | 压扁树高，查询越勤树越平 |
| 按秩合并/按大小合并 | 合并时把矮树挂到高树下 | 避免树越摞越高 |
| 两者结合 | — | 单次操作均摊 O(α(n))，近似常数 |
α(n) 是阿克曼反函数，对现实中的任何数据规模它都不会超过 4——可以认为做了双优化的并查集，单次操作就是常数时间。这也是它在竞赛和工程里都能放心大规模使用的原因。
按秩合并需要额外维护秩数组，实现时多几行；按大小合并更直观，维护每个集合的元素个数即可。二者选哪个效果差异可以忽略，顺手用哪个都行。
给工程实现加双优化的完整步骤只有三步：
- 初始化时除了 parent 数组，再建一个 rank 或 size 数组，全部置 0 或 1；
- union 时先比较两棵树的秩，把矮树挂到高树下；秩相同则任挂其一并把被挂方秩加一；
- 只有当两棵树秩相等时才增加秩，其余情况秩不变，防止树高失控。
写完后用极端数据自测一遍：把 10 万个元素按 1-2、2-3、3-4 串成一条链再查询末尾元素，响应应是瞬间完成——如果出现可感知的卡顿，说明压缩逻辑没生效。
它在真实工程里出现在哪
并查集的应用场景有一个共同模式：动态地合并分组，并随时回答”谁和谁是一伙的”。凡是能套进这个模式的问题，它都有一席之地：
| 场景 | 问题形态 | 并查集承担的角色 |
|---|---|---|
| Kruskal 最小生成树 | 加边是否成环 | 合并前查根，同根即跳过 |
| 社交网络朋友圈 | 动态加好友求分组数 | 每次有效合并，分量计数减一 |
| 节点上下线连通性 | 剩余节点是否连通 | 离线倒序加边，天然匹配并查集 |
| 图像连通区域 | 相邻同色像素归块 | 逐行扫描合并相邻块 |
同样解决连通问题，并查集和它的替代方案各有领地，选错工具会付出数量级的性能代价：
| 方案 | 单次查询 | 动态合并 | 适用边界 |
|---|---|---|---|
| 并查集 | 近似常数 | 支持 | 动态加边、只需判连通 |
| BFS/DFS 遍历 | O(n+m) | 不支持，每次重建 | 静态图、需要具体路径 |
| LCA/重链剖分 | O(log n) | 不支持 | 需要查询树上任意两点关系 |
- 图论算法：Kruskal 求最小生成树时，用并查集判断加一条边会不会成环；
- 社交网络：好友关系的传递闭包，快速求出”朋友圈”个数；
- 网络运维：机房节点动态上下线时，判断剩余节点是否仍然连通；
- 图像处理：像素连通区域标记，把相邻同色像素合并成同一块；
- 编译器与虚拟机：等价类合并，比如类型推断里的变量等价关系。
一个典型的工程案例是离线删边问题。图上不断删边、每次删完问还剩几个连通分量——删边本身没有高效算法，但把时间倒过来变成”不断加边”，就用上了并查集：每成功合并一次，连通分量个数减一。
def count_components(n, edges):
parent = list(range(n))
count = n
for a, b in edges:
ra, rb = find(a), find(b)
if ra != rb:
parent[rb] = ra
count -= 1 # 每次有效合并，分量数减一
return count这类”正着做很难、反着做很简单”的转化，是并查集很见功力的用法，也是面试和竞赛里的高频考点。
常见问题（FAQ）
Q1：为什么并查集比图遍历快？
遍历每次都要 O(n+m)，并查集合并与查询均摊近似常数，适合频繁动态合并的场景。
Q2：单次操作怎么做到接近常数时间？
路径压缩加按秩合并使树高被压到近乎扁平，均摊复杂度是阿克曼反函数级。
Q3：并查集能不能删除一条边？
原生不支持删边，需离线倒序处理或改用可持久化等变体来实现。
