【数据结构】并查集 Disjoint-Set

并查集(Disjoint Set)是一种动态维护若干个不相交的集合,导论上叫做真·用于不相交集合的数据结构】。

关于它的一个很好的例子来源以一位dalao级人物,当时我就理解了并查集,但是一直不怎么会写,现在来填这个坑。

这次参考了《算法竞赛进阶指南》以及自己的一些理解。

DS支持两种基本操作:

①get(通称find),查询一个元素属于哪一个集合

②merge(通称join),把两个集合合并成一个大集合

为了实现这种数据结构,我们采用 “代表元” 法,为每个集合选择一个固定元素,作为整个集合的代表(老大)。

关系的表示方法:

第一种思路:维护一个数组f,用f[x]保存x所在的集合的“爸爸”。这种方法可以快速查询O(1),但是合并时却需要修改大量元素的f值,效率低。

第二种思路:用树形结构保存每个集合,树上的结点就是一个元素,树根就是集合的“爸爸”,整个DS就是一片森林(不相交集合森林)。我们仍用一个数组fa来记录森林,用fa[x]保存x的爸爸。特别地,令树根的fa就是它本身。这样一来,在合并时只需连接两个树根(令其中一个爸爸成为另一个爸爸的儿子,俗称叫爸爸,fa[root_{1}] = root_{2})。不过这样却在查找时出现问题,因为树可能成为一条长长的链,这样查找就是O(n)了,效率低。

为了提高查询效率,DS引入了路径压缩按秩合并。

因为第一种查询效率高,第二种合并效率高,那么咱们就两种一起用,因为树的形态并不影响最后的使用,咱们让树根爸爸的孙子,重孙子等都成为他的儿子,即爸爸直接指向所有的结点,也就是每次在get操作的同时,把访问过的每个结点都直接指向树根。这通称路径压缩。在摊还的意义下,复杂度为O(\log N)

还有按秩合并,也称启发式合并,具体操作请看《算法导论》,在摊还的意义下,复杂度也为O(\log N)

而这两种方法可以同时使用,此时摊还的意义下,复杂度为O(\alpha (N))\alpha (N)为反阿克曼函数,是一个增长非常慢的函数,对于\forall N \leq 2^{2^{10^{19729}}},都有\alpha (N) \leq 5,所有这里可以看成一个常数。

 

实现:

①储存,使用一个数组fa保存父结点

int fa[MAXN];

②初始化,让所有元素自成一个独立集合

for(int i = 1;i <= n;i++){
    fa[i] = i;
}

③get操作,若x时树根,则x就是集合代表,否则递归访问fa[x]直至根结点

int get(int x){
    if(x == fa[x]){
        return x;
    }
    return fa[x] = get(fa[x]);//路径压缩,fa直接赋值为代表元素 
}

④merge操作,让x的树根成为y的树根的子结点

void merge(int x,int y){
    fa[get(x)] = get(y);
}

 

发布者:Cinema

成功的道路并不狭窄,因为大部分人都在颓废。

留下评论

电子邮件地址不会被公开。 必填项已用*标注