1.普通的并查集

查找：

int find(int x){
return x==fa[x]?x:find(fa[x]);//如果父节点不是自己，那么去找父节点的父节点
}

合并：

for(int i=1;i<=n;i++)fa[i]=i;//预处理
x=read();y=read();//读入
if(find(x)!=find(y))//如果不是同一个并查集的话才需要合并
    fa[find(x)]=find(y);//把x作为子节点 合并到y中

2.路径压缩 

合并方法相同，查找方法不同； 

路径压缩 查找更快了 但是 破坏了树的形状；

复杂度分析参考：数据结构学习 并查集讲解（思路，时间复杂度）

int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}

3.启发式合并（按秩合并）

启发式合并 是 高度小的集合 合并到 高度大的集合中，高度max=logn；

启发式合并不能用路径压缩 （因为路径压缩会破坏树的形状）；

查找方法同普通的并查集；

合并：

int height[maxn];
void ini(){
for(int i=1;i<=n;i++)fa[i]=i;//在主函数中预处理
}
void merge(int x,int y){
    x=find(x);y=find(y);
    if(height[x]>height[y])fa[y]=x;
    else{
    fa[x]=y;
    if(height[x]==height[y])height[y]++;
    }
}

4.带权值的并查集（路径压缩）

合并与普通的并查集相同；

查找：

int find(int x){
    if(x==fa[x])return x;
    int t=fa[x];
    fa[x]=find(fa[x]);
	v[x]+=v[t];//权值修改
    return fa[x];
}

5.例题：#4668. 冷战

冷战 - 题目 - 黑暗爆炸OJ (darkbzoj.tk)

（题目之后补全）