01先从一个问题出发
朋友圈不断合并时，快速回答两个人是否已经在同一个圈子。
一个具体的例子
合并 (0,1)、(2,3)、(1,2) 后，0 和 3 的代表相同，因此连通。
02最直接的办法，为什么慢？
每次询问连通性，都重新进行 BFS。
暴力 · O(V+E) / 次
图不断加边、询问很多时，重复搜索整张图成本很高。
03一步步，推导出优化思路
1
发现可以复用的信息
每个集合选一个根作为代表，父指针连接到根。
2
建立可维护的状态
find 走父指针，路径压缩把中途节点直接拉近根。
3
消除重复工作
union 按大小把小树接到大树，减少未来查询深度。
贯穿算法的不变量
两个节点连通，当且仅当 find 得到相同的根。
04让每一步，都看得见
试着先预测下一步，再点击「下一步」验证。变量、动画与代码会同步变化。
Union Find交互演示
STEP 01 / 16无向图 · 源点 0 · 邻居按编号处理
当前处理已处理 / 已确定未处理
01
每个节点最初独立成为一个集合。按图中边的输入顺序合并。
union_find.py参考实现 · 当前第 2 行
正在载入代码编辑器…
动画展示参考实现的执行轨迹。切换语言时，当前操作会定位到对应代码行。
05复杂度，来自具体的工作量
时间复杂度
初始化 O(V)，每条边调用 find 并至多一次合并。路径压缩 + 按大小合并的单次操作摊还为 O(α(V))，α 是增长极慢的反阿克曼函数。
辅助空间
parent 和 size 数组各有 V 项。
06看到什么，应该想到它？
关键词只是线索，继续检查适用条件07这些细节，容易踩坑
01
合并的是根
不要直接连接任意节点，否则可能破坏集合关系。
02
不适合直接删边
基本并查集只适合合并；删边需离线技巧或更复杂结构。
08把想法带进真实题目
先说出模式和适用条件，再开始写代码。
09不用背模板，回答这几个问题
01如何判断两个节点连通？
02路径压缩改变连通性吗？
03同集合内再加一条边，分量数怎么变？
你已经走完了这次推导。
能用自己的话解释复杂度和不变量，再标记为掌握。