并查集
普通并查集
先看一个问题：
P1551 亲戚
genjoedoam
规定：\(x\) 和 \(y\) 是亲戚，\(y\) 和 \(z\) 是亲戚，那么 \(x\) 和 \(z\) 也是亲戚。如果 \(x\)，\(y\) 是亲戚，那么 \(x\) 的亲戚都是 \(y\) 的亲戚，\(y\) 的亲戚也都是 \(x\) 的亲戚。现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。
我们令 \(f_i\) 为节点 \(i\) 的父亲。一开始，\(f_i=i\)，因为最开始 \(i\) 的父亲不是任何人。
接下来开始维护“合并”操作。对于一条“\(x\) 是 \(y\) 的亲戚”的一条信息，不妨设 \(x\) 是 \(y\) 的父亲，此时我们爬树找到 \(y\) 的“祖先”（可以发现，并查集建完之后是一个森林，就相当于找到节点 \(y\) 所在的树的根节点），记为 \(fy\)，将 \(f_{fy}\) 设为 \(x\) 所在树的根节点即可。
int find(int x){//寻找 x 所在树的根节点
if(f[x]==x){
return f[x];
}
else{
return find(f[x]);
}
}
int merge(int x,int y){//将 y 所在的集合（树）合并到 x 所在的集合（树）
int fx=find(x),fy=find(y);
f[fy]=fx;
}
那么“查询” \(x\) 和 \(y\) 是否在同一个集合内。我们不断从节点 \(x\) 和节点 \(y\) 向上爬树，如果他们的祖先相同，那么必定在一棵树内，即具有亲戚关系，否则就不具有亲戚关系。
bool query(int x,int y){//查询 x 与 y 是否在一个集合
if(find(x)==find(y)){
return 1;
}
return 1;
}
并查集的路径压缩优化
为什么要路径压缩？
考虑并查集的这种情况：
这样的话，每次查询操作的时间复杂度就会退化为线性。
那么怎么进行路径压缩？
我们每次查询的时候直接把查询一路上的所有点的 \(f\) 值直接设为最终查询的结果即可。
我们对上图进行路径压缩：
代码如下：
int find(int x){
if(f[x]!=x){
f[x]=find(f[x]);//路径压缩，即将每个访问路径上的点的父亲都直接设为这棵树的根节点
}
return f[x];
}
优化了整整 \(100ms\)。