并查集

一、定义

并查集是一种树型的数据结构,用于处理一些不相交集合(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操作复杂度可进一步降低到

即为 阿克曼函数

②如果题目需要维护明确的父子关系而用到了按秩合并的话,是不能用路径压缩的。一旦用了路径压缩,会破坏树的形态,原来的节点会直接压缩到祖先上,这样一来我们调用的时候父子关系发生了改变,造成了算法的错误。

③并查集能在一张无向图中维护节点之间的连通性(实际上可以维护许多具有传递性的关系)。

④并查集能够快速跳过无用集合

普通并查集:

P1955 [NOI2015]程序自动分析

UVA1316 Supermarket

边带权并查集:

P1196 [NOI2002]银河英雄传说

POJ 1733 Parity game

扩展域并查集:

P2024 [NOI2001]食物链

POJ 1733 Parity game

02-01 03:17