🔑 并查集为什么几乎总是够快
并查集这个名字听起来像某种“高级数据结构”，但它真正解决的问题很朴素：有一堆元素，它们一开始彼此独立，后来你不断收到“把 A 和 B 归到一组”的指令，同时还要不停地问“X 和 Y 现在是不是同一组”。如果每次都真的把整组元素搬来搬去，代价会越来越大，所以并查集的设计思路很直接：每个集合只认一个代表元，元素只需要沿着父指针一路找到这个代表元就行。
问题在于，如果你什么都不管，父指针可能退化成一条长链。这样一来，查一次代表元就像顺着一根很长的绳子往上爬，越查越慢。并查集之所以好用，不是因为它会“合并”，而是因为它在合并和查询时偷偷做了两件事。第一件事叫 union by rank 或 union by size，本质就是别乱挂，把小树挂到大树下面，别反过来。第二件事叫 path compression，也就是路径压缩：当你终于找到根节点后，顺手把沿路所有节点都直接改成指向根。下次再查，这条路几乎就消失了。
这就是它“几乎总是够快”的原因。它不是靠一次查询特别快，而是靠每次查询都顺手把未来的查询变便宜。很多初学者会把它想成一个静态结构，其实并查集很像带自我修复能力的森林。你查得越多，结构反而越扁，后面的操作越轻。算法分析里常说它的均摊复杂度接近常数，严格写法是和反阿克曼函数有关。这个名字看着吓人，但你可以把它理解成：在真实世界的数据范围里，它慢不到哪里去，基本可以当成 O(1) 用。
并查集特别适合处理“连通性只会增加不会撤销”的场景，比如 Kruskal 最小生成树、社交网络分组、离线判断图中两点是否连通。它不擅长的地方也很明确：如果你想支持“删除一条关系”或者频繁拆分集合，并查集就不对路了，因为它只会把树压得更扁，不会帮你优雅地拆回来。很多人踩坑，不是代码写错，而是拿它去解决动态删除问题，那方向从一开始就偏了。
🧪 课后一题：有 6 个点，初始各自独立。依次执行 union(1,2)、union(2,3)、union(4,5)，然后问 find(1) == find(3) 和 find(1) == find(5) 的结果分别是什么？答案：
💡 易混淆点：并查集判断的是“是否属于同一连通分量”，不是“1 和 3 之间是否存在一条直接边”。
#CS
并查集这个名字听起来像某种“高级数据结构”，但它真正解决的问题很朴素：有一堆元素，它们一开始彼此独立，后来你不断收到“把 A 和 B 归到一组”的指令，同时还要不停地问“X 和 Y 现在是不是同一组”。如果每次都真的把整组元素搬来搬去，代价会越来越大，所以并查集的设计思路很直接：每个集合只认一个代表元，元素只需要沿着父指针一路找到这个代表元就行。
问题在于，如果你什么都不管，父指针可能退化成一条长链。这样一来，查一次代表元就像顺着一根很长的绳子往上爬，越查越慢。并查集之所以好用，不是因为它会“合并”，而是因为它在合并和查询时偷偷做了两件事。第一件事叫 union by rank 或 union by size，本质就是别乱挂，把小树挂到大树下面，别反过来。第二件事叫 path compression，也就是路径压缩：当你终于找到根节点后，顺手把沿路所有节点都直接改成指向根。下次再查，这条路几乎就消失了。
这就是它“几乎总是够快”的原因。它不是靠一次查询特别快，而是靠每次查询都顺手把未来的查询变便宜。很多初学者会把它想成一个静态结构，其实并查集很像带自我修复能力的森林。你查得越多，结构反而越扁，后面的操作越轻。算法分析里常说它的均摊复杂度接近常数，严格写法是和反阿克曼函数有关。这个名字看着吓人，但你可以把它理解成：在真实世界的数据范围里，它慢不到哪里去，基本可以当成 O(1) 用。
并查集特别适合处理“连通性只会增加不会撤销”的场景，比如 Kruskal 最小生成树、社交网络分组、离线判断图中两点是否连通。它不擅长的地方也很明确：如果你想支持“删除一条关系”或者频繁拆分集合，并查集就不对路了，因为它只会把树压得更扁，不会帮你优雅地拆回来。很多人踩坑，不是代码写错，而是拿它去解决动态删除问题，那方向从一开始就偏了。
🧪 课后一题：有 6 个点，初始各自独立。依次执行 union(1,2)、union(2,3)、union(4,5)，然后问 find(1) == find(3) 和 find(1) == find(5) 的结果分别是什么？答案：
💡 易混淆点：并查集判断的是“是否属于同一连通分量”，不是“1 和 3 之间是否存在一条直接边”。
#CS
