算法概念速查
什么是并查集？合并与查询近 O(1) 的原理与经典例题
一句话定义
并查集（Union-Find）是一种只干两件事的数据结构：把两个集合合并（union）、查询两个元素是否属于同一集合（find）。实现上让每个节点记住自己的父节点，树根就是集合的代表；配合路径压缩和按秩合并，单次操作均摊接近 O(1)。它是处理「连通块 / 朋友圈 / 动态加边判环」类问题的利器。
先打个比方
认帮派只认大哥：想知道两个人是不是一伙的，各自顺着「我的上级」一路问到最顶上的大哥，大哥是同一个人就是一伙。两个帮派合并，就是让其中一个大哥认另一个大哥当老大。路径压缩相当于问过一次之后，把沿途所有人直接改挂到大哥名下——下次再问一步到位。
它是怎么运作的
find(x) 沿父指针爬到根；union(x, y) 先各自 find 到根，根不同就把一棵树挂到另一棵下面。裸实现的树可能退化成链，两个优化把它救回来：路径压缩（find 时把沿途节点直接指向根）和按秩合并（矮树挂到高树下），加起来单次操作均摊 α(n)——反阿克曼函数，实际当常数用。
最经典的判环用法：无向图逐条加边，每条边 (u, v) 先查 find(u) 是否等于 find(v)——相等说明 u、v 早已连通，这条边一加必成环；不等就 union 起来。冗余连接（LC684）整题就是这一个判断。
什么时候用：识别信号
题目里出现下面任何一条，就该想到「并查集」。
- 问「朋友圈 / 省份 / 连通块」的个数或大小
- 边是动态一条条加入的，加边过程中要随时回答连通性（离线一次建好图的场景 DFS 也行）
- 无向图加边判环：这条边加上去会不会成环
- 等式 / 关系有传递性要合并：等式方程的可满足性、账户合并
别和它们搞混
vs DFS / BFS 求连通块
图是静态的、一次性数连通块，DFS 扫一遍就够；边动态加入、查询穿插在修改之间时，DFS 每查一次要重扫全图，并查集近 O(1) 完胜。
vs 有向图判环
并查集只认「连通」不认方向，只能判无向图的环；有向图判环要用拓扑排序（入度法）或 DFS 三色标记。拿并查集判有向环是常见误用。
配套动画题：眼见为实
每道题都有逐步交互动画，看着数据动起来，比读十遍文字都快。
常见追问
路径压缩到底压缩了什么？
find 的回溯路上，把沿途每个节点的父指针直接改成根。树被「拍扁」成一层，后续任何一次 find 都几乎一步到根。两行代码换来近 O(1)，是性价比最高的优化。
并查集能删边（拆散集合）吗？
不能，合并是单向的、信息在压缩中已丢失。遇到要删边的题，常用套路是离线倒序处理：把删边序列反过来，变成「从零开始逐条加边」。
什么时候用并查集、什么时候直接 DFS？
一句话：静态图用 DFS，动态加边用并查集。另外只问连通性（是否一伙）用并查集就够；要拿到具体路径，还是得 DFS/BFS。