并查集
并查集支持的操作：
- 将两个集合合并
- 查询两个元素是否在同一个集合中
暴力做法：用一个数组来存储元素 x 对应的集合编号 k，即 belong[x] = k;
- 将两个集合合并：
，需要将所有满足 belong[x] = t;的编号改为k，需要遍历所有数据 - 查询操作：
并查集可以在近乎
思想：用树的形式来维护各个集合：
- 每个集合的编号用根节点的编号来表示
- 每个节点都存储它的父节点编号
p[x]
问题：
- 如何判断是否为树根？可以定义树根满足
p[x] == x - 如何求某个节点
x的集合编号？while (p[x] != x) x = p[x];只要不是树根就一直往上走 - 如何合并两个集合？把其中一个集合作为另一个集合树根的儿子即可
p[a] = b;注意a, b都是集合编号
此时仍然存在问题，查询集合编号与并查集树的高度息息相关，远远达不到
路径压缩：当我们查询到某个节点的编号后，将该查询路径上的所有点的父节点都 直接指向根节点！进行这个优化后，并查集的时间复杂度已经近似
cpp
int find(int x) {
// 返回 x 的集合编号 + 路径压缩
if (p[x] != x) {
p[x] = find(p[x]); // 将一串捋成了一挂
}
return p[x];
}核心函数：只要不是根节点，就递归查找父节点的集合编号。
连通块中点的数量
维护的 size[] 数组只考虑根节点，表示连通块中点的数量。