并查集这个名字听起来像某种“高级数据结构”,但它真正解决的问题很朴素:有一堆元素,它们一开始彼此独立,后来你不断收到“把 A 和 B 归到一组”的指令,同时还要不停地问“X 和 Y 现在是不是同一组”。如果每次都真的把整组元素搬来搬去,代价会越来越大,所以并查集的设计思路很直接:每个集合只认一个代表元,元素只需要沿着父指针一路找到这个代表元就行。
问题在于,如果你什么都不管,父指针可能退化成一条长链。这样一来,查一次代表元就像顺着一根很长的绳子往上爬,越查越慢。并查集之所以好用,不是因为它会“合并”,而是因为它在合并和查询时偷偷做了两件事。第一件事叫 union by rank 或 union by size,本质就是别乱挂,把小树挂到大树下面,别反过来。第二件事叫 path compression,也就是路径压缩:当你终于找到根节点后,顺手把沿路所有节点都直接改成指向根。下次再查,这条路几乎就消失了。