并查集解决什么问题
并查集（Union-Find）是一种树形数据结构，用于处理不相交集合的合并与查询问题。简单说，它回答两个问题：元素A和元素B是否属于同一个集合？以及如何将两个集合合并成一个？。生活类比：一个班级里，同学们按朋友圈分成几个小团体，并查集能快速知道两个人是否在同一个朋友圈，也能把两个朋友圈合并。
两大操作：find 找根 与 union 合并
find(x)：找到元素x所在集合的“代表元素”（根节点）。每个集合用一棵树表示，根节点是集合的标识。如果两个元素的根相同，它们就在同一集合。
union(x, y)：将x和y所在的集合合并。做法是把一棵树的根挂到另一棵树的根上，成为其子节点。
初始时，每个元素自己就是一个集合，自己的父节点指向自己。
优化：路径压缩与按秩合并
为了让树更“矮”，提高效率，有两种常用优化：
- 路径压缩：在执行find时，将沿途所有节点直接指向根节点。这样下次查找更快。
- 按秩合并：union时，将“秩”（树的高度或大小）较小的树挂到较大的树下，避免树长高。
两种优化一起用，效果最佳。
复杂度（近似 O(1)）
| 操作 | 平均时间复杂度 | 最坏时间复杂度 |
|---|---|---|
| find（无优化） | O(log n) | O(n) |
| union（无优化） | O(log n) | O(n) |
| find（路径压缩+按秩合并） | O(α(n)) | O(α(n)) |
| union（路径压缩+按秩合并） | O(α(n)) | O(α(n)) |
其中 α(n) 是反阿克曼函数，增长极慢，对于实际所有n，α(n) ≤ 5，所以可以认为近似 O(1)。
典型应用：朋友圈/连通分量/Kruskal
- 朋友圈问题：给定好友关系，判断两个人是否在同一个朋友圈（连通分量）。并查集可快速合并和查询。
- 连通分量：在图中，并查集可以高效统计连通分量的个数，或判断两个节点是否连通。
- Kruskal最小生成树算法：按边权从小到大加入边，用并查集判断加入的边是否会形成环（即两个端点是否已在同一集合），从而避免环。