并查集
一、定义
并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。
集合定义方法： “代表元法”，即 每个集合选择一个固定的元素，作为整个集合的“代表”。
二、基本操作
Find —— 查询一个元素属于哪一个集合
Merge —— 把两个集合合并成一个大集合
代码示例：
三、路径压缩与按秩合并
——并查集的 奇技淫巧
①路径压缩
Get时， 将访问过的节点直接指向树根。 均摊复杂度
代码示例：
int find(int x) { return x == fa[x] ? fa[x] : fa[x] = find(fa[x]); }
按秩合并
“秩”：树的深度(未路径压缩) / 集合大小 。均摊复杂度
将”秩“记录在 “代表元素” ， 合并时， 将“秩”较小的树根 作为 “秩”较大的树根的子节点。
代码示例：
void unionn(int x, int y){//按大小合并
int u=Get(x), v=Get(y);
if(u != v) {
if(size[u]<size[v]) f[u]=v, size[v]+=size[u];//按大小合并每次要更新大小
else f[v]=u, size[u]+=size[v];
}
}
void unionn(int x, int y){//按深度合并
int u=Get(x), v=Get(y);
if(u != v) {
if(high[u] < hige[v]) f[u] = v;
else {
f[v]=u;
if(high[u]==high[v]) high[u]++;//按深度合并只有在两树高度相等的时候更新
}
}
}
注：
①同时采用 “路径压缩” 和 “按秩合并” 优化的并查集， 每次Get操作复杂度可进一步降低到。
即为 反阿克曼函数
②如果题目需要维护明确的父子关系而用到了按秩合并的话，是不能用路径压缩的。一旦用了路径压缩，会破坏树的形态，原来的节点会直接压缩到祖先上，这样一来我们调用的时候父子关系发生了改变，造成了算法的错误。
③并查集能在一张无向图中维护节点之间的连通性(实际上可以维护许多具有传递性的关系)。
④并查集能够快速跳过无用集合
普通并查集：
边带权并查集：
扩展域并查集：