并查集(Union-Find)

定义

并查集（Union-Find，又称不相交集合）是一种维护若干不相交集合的数据结构，支持两种核心操作：合并两个集合（union），以及查询某元素所属集合的代表（find）。

原理

并查集用森林表示，每个集合是一棵树，根节点作为该集合的代表。find 沿父指针上溯找到根；union 把一棵树的根挂到另一棵树的根下。为避免树退化，采用两种优化：路径压缩在 find 时把路径上的节点直接指向根；按秩合并总是把矮树挂到高树下。两者结合后，单次操作的均摊复杂度接近常数。

复杂度

• find/union（带优化均摊）：接近 O(1)，记为 O(α(n))
• 空间复杂度：O(n)

应用场景

• 判断图的连通性
• Kruskal 最小生成树
• 动态连通性问题
• 等价类划分与朋友圈合并