🔑 并查集为什么几乎总和“路径压缩”绑在一起
并查集解决的不是“找元素”，而是“判断两个东西是不是已经连在一起”。你可以把它理解成一堆集合在不断合并：今天把 a 和 b 连起来，明天把 b 和 c 连起来，后天再问 a 和 c 是不是同一组。如果每次都真的把整组数据搬来搬去，代价会很大，所以并查集故意只存一件事：每个点先指向一个“父节点”，最后一路走到代表整个集合的根。
它聪明的地方不在“能合并”，而在“合并很多次以后还能查得快”。如果你只是傻傻地把一个根挂到另一个根下面，树可能越长越歪，最后一次 find(x) 得一路爬很多层，性能会烂掉。路径压缩就是干这个脏活的：你既然已经顺着父指针爬到了根，那回头时就把路上的节点直接改成指向根。下次再查这些节点，基本一跳就到。也就是说，它不是靠更复杂的结构取胜，而是靠“查过一次就顺手把结构修平”。
这就是为什么并查集在动态连通性问题里这么常见，比如 Kruskal 最小生成树、朋友圈合并、岛屿连通、账号归并。真正重要的不是“集合”这个词，而是“合并关系会越来越多，查询也会越来越频繁”。路径压缩让这个结构越用越顺，而不是越用越重。
容易踩坑的地方也很直接。第一，union(a, b) 不是把 a 挂到 b，而是把 find(a) 的根和 find(b) 的根合并；如果你直接拿原节点乱连，整棵树就坏了。第二，路径压缩优化的是 find，不是 union 本身，所以很多代码看起来像“查找函数偷偷改了数据”，这不是副作用失控，这是设计本意。第三，如果题目需要维护集合大小、边数、权值差，你不能只会裸模板，因为额外信息要么挂在根上，要么在路径压缩时一起更新，不然答案会错得很隐蔽。
🧪 课后一题：有 6 个点，初始各自独立。依次执行 union(1,2)、union(2,3)、union(4,5)、union(3,5)。这时 1 和 5 是否连通？2 和 6 是否连通？答案：
💡 易混淆点：并查集只能高效处理“是否属于同一连通块”这类问题，不能直接告诉你两点之间的具体路径长什么样。
#CS
并查集解决的不是“找元素”，而是“判断两个东西是不是已经连在一起”。你可以把它理解成一堆集合在不断合并：今天把 a 和 b 连起来，明天把 b 和 c 连起来，后天再问 a 和 c 是不是同一组。如果每次都真的把整组数据搬来搬去，代价会很大，所以并查集故意只存一件事：每个点先指向一个“父节点”，最后一路走到代表整个集合的根。
它聪明的地方不在“能合并”，而在“合并很多次以后还能查得快”。如果你只是傻傻地把一个根挂到另一个根下面，树可能越长越歪，最后一次 find(x) 得一路爬很多层，性能会烂掉。路径压缩就是干这个脏活的：你既然已经顺着父指针爬到了根，那回头时就把路上的节点直接改成指向根。下次再查这些节点，基本一跳就到。也就是说，它不是靠更复杂的结构取胜，而是靠“查过一次就顺手把结构修平”。
这就是为什么并查集在动态连通性问题里这么常见，比如 Kruskal 最小生成树、朋友圈合并、岛屿连通、账号归并。真正重要的不是“集合”这个词，而是“合并关系会越来越多，查询也会越来越频繁”。路径压缩让这个结构越用越顺，而不是越用越重。
容易踩坑的地方也很直接。第一，union(a, b) 不是把 a 挂到 b，而是把 find(a) 的根和 find(b) 的根合并；如果你直接拿原节点乱连，整棵树就坏了。第二，路径压缩优化的是 find，不是 union 本身，所以很多代码看起来像“查找函数偷偷改了数据”，这不是副作用失控，这是设计本意。第三，如果题目需要维护集合大小、边数、权值差，你不能只会裸模板，因为额外信息要么挂在根上，要么在路径压缩时一起更新，不然答案会错得很隐蔽。
🧪 课后一题：有 6 个点，初始各自独立。依次执行 union(1,2)、union(2,3)、union(4,5)、union(3,5)。这时 1 和 5 是否连通？2 和 6 是否连通？答案：
💡 易混淆点：并查集只能高效处理“是否属于同一连通块”这类问题，不能直接告诉你两点之间的具体路径长什么样。
#CS
