🔑 并查集为什么几乎总比你手写连通性判断更对
并查集（Union-Find）解决的是一个很朴素的问题：一堆元素不断被“连起来”之后，你想快速知道两个元素现在是不是属于同一组。它看起来像是个小技巧，真正厉害的地方在于设计思路很干净：它根本不关心这组里具体长什么样，也不关心连接路径是什么，只维护“谁和谁最终属于同一个代表元”。这就是它快的原因——它只保存判断连通性所必需的信息，别的都不存。
如果你自己硬写，最容易走进一条烂路：每次合并两组时，把整组元素重新扫描、重编号，或者用图搜索临时判断连通。这样在数据量一大、操作一多时，很快就会慢得离谱。并查集的做法更像是偷懒到极致：每个集合选一个根节点，元素只需要一路找到根，就知道自己属于哪一组；合并时，也只是让一个根指向另一个根。核心操作只有两个，find 找根，union 合并根。
但裸的并查集还不够好。真正让它“几乎等于 O(1)” 的，是 path compression 和 union by rank/size。path compression 的意思是：你查一次根，就顺手把沿途节点直接挂到根上，下次再查就更短。union by size 的意思是：小树挂大树，别反过来。为什么这样设计？因为所有性能问题本质上都来自树太高。你不控制高度，find 就会退化成一长串父指针追踪，最后跟链表没区别。
这里最容易踩坑的地方，不是原理，而是实现细节。第一种坑是把 union(x, y) 写成 parent[x] = y，这几乎总是错的，因为 x 和 y 可能都不是根，你是在随手改中间节点，结构会变脏。正确做法是先找 rootX 和 rootY，再决定谁挂谁。第二种坑是以为 path compression 会改变“集合内容”，其实不会，它改的是树形结构，不改连通关系。第三种坑是把并查集拿去做删除边、撤销合并这类操作；这就超出它的舒适区了，因为它擅长的是只增不减的连通性维护，不擅长回滚和动态拆分。
这东西为什么在算法里反复出现？因为很多问题的本质不是“图怎么走”，而是“关系是否已经连上”。Kruskal 最小生成树要它，是因为它只关心加一条边会不会形成环；账户合并、朋友圈、岛屿连通、网络分组也要它，因为这些问题都在反复问同一句话：这两个东西现在是不是同一类。你一旦看清问题本质只是“分组归属”，就别再上来就建整张图然后 DFS/BFS，那个数据结构已经重了。
🧪 课后一题：有 6 个元素，初始各自独立。依次执行 union(1,2)、union(2,3)、union(4,5)、union(3,5)。最后 1 和 5 是否连通？集合一共有几个？
💡 易混淆点：并查集只能高效回答“是否同组”和“合并分组”，它通常不能直接告诉你两点之间的具体路径，更不适合处理删除关系后的连通性变化。
#CS
并查集（Union-Find）解决的是一个很朴素的问题：一堆元素不断被“连起来”之后，你想快速知道两个元素现在是不是属于同一组。它看起来像是个小技巧，真正厉害的地方在于设计思路很干净：它根本不关心这组里具体长什么样，也不关心连接路径是什么，只维护“谁和谁最终属于同一个代表元”。这就是它快的原因——它只保存判断连通性所必需的信息，别的都不存。
如果你自己硬写，最容易走进一条烂路：每次合并两组时，把整组元素重新扫描、重编号，或者用图搜索临时判断连通。这样在数据量一大、操作一多时，很快就会慢得离谱。并查集的做法更像是偷懒到极致：每个集合选一个根节点，元素只需要一路找到根，就知道自己属于哪一组；合并时，也只是让一个根指向另一个根。核心操作只有两个，find 找根，union 合并根。
但裸的并查集还不够好。真正让它“几乎等于 O(1)” 的，是 path compression 和 union by rank/size。path compression 的意思是：你查一次根，就顺手把沿途节点直接挂到根上，下次再查就更短。union by size 的意思是：小树挂大树，别反过来。为什么这样设计？因为所有性能问题本质上都来自树太高。你不控制高度，find 就会退化成一长串父指针追踪，最后跟链表没区别。
这里最容易踩坑的地方，不是原理，而是实现细节。第一种坑是把 union(x, y) 写成 parent[x] = y，这几乎总是错的，因为 x 和 y 可能都不是根，你是在随手改中间节点，结构会变脏。正确做法是先找 rootX 和 rootY，再决定谁挂谁。第二种坑是以为 path compression 会改变“集合内容”，其实不会，它改的是树形结构，不改连通关系。第三种坑是把并查集拿去做删除边、撤销合并这类操作；这就超出它的舒适区了，因为它擅长的是只增不减的连通性维护，不擅长回滚和动态拆分。
这东西为什么在算法里反复出现？因为很多问题的本质不是“图怎么走”，而是“关系是否已经连上”。Kruskal 最小生成树要它，是因为它只关心加一条边会不会形成环；账户合并、朋友圈、岛屿连通、网络分组也要它，因为这些问题都在反复问同一句话：这两个东西现在是不是同一类。你一旦看清问题本质只是“分组归属”，就别再上来就建整张图然后 DFS/BFS，那个数据结构已经重了。
🧪 课后一题：有 6 个元素，初始各自独立。依次执行 union(1,2)、union(2,3)、union(4,5)、union(3,5)。最后 1 和 5 是否连通？集合一共有几个？
💡 易混淆点：并查集只能高效回答“是否同组”和“合并分组”，它通常不能直接告诉你两点之间的具体路径，更不适合处理删除关系后的连通性变化。
#CS
