🔑 并查集为什么几乎总是“快得像 O(1)”

很多人第一次看到并查集，会以为它只是一个“把元素分组”的小工具：find(x) 看看 x 属于哪一组，union(a, b) 把两组合起来。真正有意思的地方不在功能，而在它的设计很狡猾。它不试图让每一步都绝对平衡，也不急着把整棵树修得漂漂亮亮，它只做两件事：合并时尽量把矮树挂到高树下面，查询时顺手把走过的路径压扁。结果就是，刚开始树可能有点歪，但你查得越多，它自己越像被“踩平”了一样，后面的查询会越来越短。

这就是为什么并查集常被用在连通性问题里，比如“两个节点现在是不是已经连起来了”“加上一条边会不会形成环”。Kruskal 最小生成树离不开它，图里动态判断连通块也离不开它。它快，不是因为每次都神奇，而是因为它把整理成本偷偷摊到未来了。你这次 find 多走了几步，没白走，路径压缩会让后面的人少走很多路。这种“顺手维护结构”的想法，比死记复杂度更重要。

很多初学者会背一句话：并查集时间复杂度接近 O(1)。这话不算错，但也容易把脑子带歪。更准确一点，它的均摊复杂度是 O(α(n))，这里的 α 是反阿克曼函数，长得很吓人，但增长慢得离谱，慢到你在现实里几乎可以把它当常数。所以工程上大家才会直接说“近似 O(1)”。但别把“近似”听成“真的随便写都行”。如果你只做路径压缩，不做按秩合并，通常也挺快；可要是两样都不做，那树就可能长成链，性能直接退化。

还有一个常见坑是，你以为并查集适合一切“分组”问题，其实不是。它只擅长处理“谁和谁连通”这种等价关系：自反、对称、传递。比如朋友关系、同一个集合、图的连通块，这些都行。但如果问题变成“谁比谁大”“依赖先后顺序”“最短路径是多少”，并查集就帮不上忙了。它只回答“是不是一伙的”，不回答“这伙人内部是什么结构”。

🧪 有 1,2,3,4,5 五个点，初始互不连通。依次执行 union(1,2)、union(2,3)、union(4,5)、union(3,5) 之后，1 和 5 是否连通？此时一共有几个连通块？答案：

💡 易混淆点：路径压缩不会改变“哪些元素属于同一集合”，它只是在重排父指针让树变矮；别把它理解成“额外做了一次合并”。

#CS