更好的阅读体验

并查集

概念

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

基本操作

1.get(find)操作 查询一个元素所属哪一个集合

2.merge合并操作,把两个集合合并成为一个集合

具体实现

使用树形结构存储每个集合,刚开始的时候每个点就是一个独立的集合,且这个集合树的树根就是本身.

//代码实现
for(int i=1;i<=n;i++)
    father[i]=i;
//father数组为这个点的父亲,刚开始也就是树根祖宗

优化方法

路径压缩:每一个执行get操作的时候,把访问过的节点(也就是所有元素的父亲),都统统指向树根祖宗.这种方法可以避免出题人刻意卡掉链式结构.复杂度$O(logn)$

//代码实现
int get(int x)
{
    return x==fa[x]?x:fa[x]=get(fa[x]);
}
//一行代码精简实现

按秩合并:秩有两种定义,一个是未压缩过的树的深度,一个是集合的大小,但是lyd大佬说,无论采用任何一种定义,我们统统可以把集合的秩记录在树根上,然后每一个合并都让秩较小的数,做法秩较大的树根子节点.$O(logn)$

//代码暂无,日后补充.

模板

void init(int n)
{
    for(int i=1;i<=n;i++)
        fa[i]=i;
}
int get(int x)
{
    return fa[x]==x?x:fa[x]=get(fa[x]);//路径压缩,防止链式结构
}
void merge(int x,int y)
{
    fa[get(x)]=get(y);
}

精简例题

AcWing 237. 程序自动分析
题解
AcWing 238. 银河英雄传说
题解

预告:下一次讲解拓展域和边带权,也就是种类并查集和边权并查集.

感谢lyd大佬的<<算法竞赛进阶指南>>