并查集

概念

并查集是一种可以动态维护若干个不重叠的结合,并且支持合并与查询的数据结构.也就是擅长维护各种各样的具有传递性质的关系.

基本操作

预处理

//使得每个节点的父亲都是自己本身
//p数组即为祖先
for(int i=1;i<=n;i++)
    p[i]=i;

求元素的祖先

while(p[x]!=x)x=p[x];

路径压缩

 int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

合并集合

px是x的集合编号,py是y的集合编号.
所有合并两个集合只需要把一个指向另外一个p可,
即:
p[find(x)]=find(y)

询问两个元素是否在同一个集合当中

一个集合里面的元素,应该具有共同的祖先,所有只需要判断两个元素的祖先是不是一样的即可.
即:
if(find(x)==find(y))

总结一下,代码即为:

int p[N]; //存储每个点的祖宗节点

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

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);

维护额外信息的并查集

每个集合中元素的个数

开另外一个数组来记录集合元素的个数.

 int p[N], size[N];
    //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        size[i] = 1;
    }

    // 合并a和b所在的两个集合：
    size[find(b)] += size[find(a)];
    p[find(a)] = find(b);

每一元素到根节点的距离

开另外一个数组来记录距离.

int p[N], d[N];
    //p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x)
        {
            int u = find(p[x]);
            d[x] += d[p[x]];
            p[x] = u;
        }
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        d[i] = 0;
    }

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);
    d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量