并查集-模板

并查集&带权并查集算法模板

并查集 | Distjoint Set

算法简介

并查集(disjoint set)，英文意为与若干集合做交互，中文就更直观的表达了对集合做合并或查询的操作。
一般情况下需要其他信息配合并查集进行维护，也就是带权并查集。
有一些算法是实现也是基于并查集的思想，比如说最小生成树的kruskal和最近公共祖先的tarjan。

存储方案

逻辑存储：使用树来表示集合的从属关系
物理存储：一个一维数组p[N],表示为某个节点的祖宗节点

代码模板

//物理存储
const int N;//数据范围
int p[N];//并查集数组

//初始化
for(int i=1; i<=n; i++) p[i] = i; //将每个节点的父节点初始化为自身

//查找 返回x的祖宗节点 + 路径压缩
int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);//递归实现路径压缩
    return p[x];
}

//合并 a的祖宗节点成为b的祖宗节点的父节点
void merge(int a, int b)
{
    //简单的合并一条语句即可，这里是为了带权并查集做准备
    //找到a和b的祖宗节点并备份
    int aa = find(a);
    int bb = find(b);
    if(aa != bb)
    {
        //树的存储中为b的祖先节点指向a的祖先节点
        p[find(b)] = find(a);
    }
}

带权并查集常见类型

这里特指需要更改merge或者find函数的类型

• 更新集合的大小 -> 绑定到根节点
• 更新到根节点的距离 -> 绑定到每个节点