Ruibin_Ningh
简介
并查集是一种用于管理元素的树形结构,其功能如其名,分别是合并(union)和查找(find)
首先我们把集合抽象成一个树,这个树的根节点是谁不重要,集合内除了这个元素外的所有元素都是这个根节点的后代(如上图示意)
并查集有两个函数:union(x,y) 和find(x,y) ,分别表示合并x和y所在的集合和查找x或y的根节点(我们把整个集合抽象成树),此时的根节点就可以表示一个集合的编号
通常定义数组fa[MAXN] 或p[MAXN] (分别是英文的Father和parent)来表示一个节点的父节点,例如fa[x] 表示x的父节点
对于根节点,它的父亲指向自己
于是并查集就这样存储下了所有的集合
核心
初始化
初始时每一个元素都是一个独立的集合,所以每一个元素都会指向自己
void Initial(int n){
for(int i=0;i<n;i++){
fa[i]=i;
}
}查询操作
我们想到可以使用递归进行查询
int find(int x){
if(fa[x]==x)return x;//如果x节点的父亲是他自己,即x节点为根
return find(fa[x]);//否则对它的父亲继续查询,直到查到根节点
}此时的查询复杂度在最坏情况大可达到$O(n)$
路径压缩
这时候我们就会发现,在查询的过程中树的高度越大,复杂度越高,于是我们要想办法把整个树的高度降下来
int find(int x){
if(fa[x]==x)return x;//如果x节点的父亲是他自己,即x节点为根
return fa[x]=find(fa[x]);//边查询边把后代指向根节点
}我们注意到可以边查询边把这个节点指向更高一级的父节点,举个例子
左边是一棵树,我们查找4号节点所属的集合,前面说了根节点就可以代表整个集合的编号,所以我们执行find(4)对4号节点所属集合进行查询,这里以文字的方式展示整个执行流程
执行 find(4)
└─ fa[4] = 2 ≠ 4，递归调用 find(2)
└─ 执行 find(2)
│ └─ fa[2] = 1 ≠ 2，递归调用 find(1)
│ └─ 执行 find(1)
│ └─ fa[1] = 1 == 1，返回 1
│ └─ find(1) 返回 1，将 2 号节点的父亲指向 1
└─ find(2) 返回 1，将 4 号节点的父亲指向 1
└─ find(4) 返回 1我们通过这样的方式边查询边降低树的高度,将查询的复杂度降到了$O(α(n))$
合并操作
假设有两个集合,我们把它们按照之前的流程编程两颗树,那么想要合并这两个集合无非就是合并这两棵树,所以我们可以把第一颗树的根节点移到第二棵树下,这样就变成了一颗树,也就是合并成了一个集合,如图所示
那么在代码层面怎么操作呢,很简单,把第一个树的根节点的父亲改成第二个树的根节点就行了,即让fa[1]=6
所以对于任意两个元素,如果我想合并他们两个所在的集合,只需要用find 函数找到根节点,再把其中一个的父亲改成另一个,易得代码
void uni(int x,int y){
int fx=find(x);
int fy=find(y);
if(fx!=fy)fa[fx]=fy;//合并的前提是两个元素不是同一集合
}按秩合并
我们讲路径压缩的时候说过,一个树越矮(高度越低)效率越高,如果我们盲目得合并可能会造成一个非常高的树,这对我们查询是不利的,甚至可能会前功尽弃(达不到最优复杂度 $O(α(n))$ )
于是我们想到可以维护一个变量记录这个树的某种特征使它在合并时可以优先选择合并成一个较矮的树,我们把这个特征值叫做"秩"
这里有两种优化思路
按照树的高度进行合并,即优先把矮的树合并在高的树下,但是这里的高度是估计高度,后面会讲到
按照树的大小进行合并,优先把小树合并在大树下面
按高度合并
我们维护一个h数组表示每一棵树的高度,即h[根节点编号] 为一棵树的高度
void uni(int x,int y){
int fx=find(x);
int fy=find(y);
if(fx==fy)return;
if(h[fx]<h[fy])fa[fx]=fy;
else if(h[fx]>h[fy])fa[fy]=fx;
else{
fa[fy]=fx;
h[fx]++; // 合并后高度增加
}
}但是为什么说是估计高度呢
在用路径压缩的时候我们会把一棵树的高度悄悄优化掉,导致h数组记录的高度并不准确
不过肯定有人问为什么不在路径压缩的时候记录高度,其实想法是好的,但是这样代价是需要极大的操作,损失了效率,得不偿失
按照大小合并
我们可以维护一个s数组记录每棵树的大小(即节点数),每次合并优先把节点数少的合并在节点数多的下面
void uni(int x,int y){
int fx=find(x);
int fy=find(y);
if(fx==fy)return;
if(s[fx]<s[fy]){
fa[fx]=fy;
s[fy]+=s[fx];
}else{
fa[fy]=fx;
s[fx]+=s[fy];
}
}我个人比较倾向按大小合并,但实际上这两种方案的复杂度都是$\mathcal{O}(\alpha(n))$
总结
代码一览
无优化版
// 1. 无优化
const int MAXN=100000;
int fa[MAXN];
int find(int x){
if(fa[x]==x) return x; // x 是根
return find(fa[x]);
}
void uni(int x,int y){
x=find(x);
y=find(y);
if(x!=y) fa[x]=y;
}
void init(int n){
for(int i=1;i<=n;i++) fa[i]=i;
}只有路径压缩
// 2. 只有路径压缩
const int MAXN=100000;
int fa[MAXN];
int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]); // 递归压缩
}
void uni(int x,int y){
x=find(x);
y=find(y);
if(x!=y) fa[x]=y;
}
void init(int n){
for(int i=1;i<=n;i++) fa[i]=i;
}只有按高合并
// 3. 只有按高合并，不做路径压缩
const int MAXN=100000;
int fa[MAXN],h[MAXN];
int find(int x){
if(fa[x]==x) return x;
return find(fa[x]);
}
void uni(int x,int y){
x=find(x);
y=find(y);
if(x==y) return;
if(h[x]<h[y]) fa[x]=y;
else if(h[x]>h[y]) fa[y]=x;
else{
fa[y]=x;
h[x]++; // 同高时高度+1
}
}
void init(int n){
for(int i=1;i<=n;i++){
fa[i]=i;
h[i]=1;
}
}只有按大小合并
// 4. 只有按大小合并，不做路径压缩
const int MAXN=100000;
int fa[MAXN],s[MAXN];
int find(int x){
if(fa[x]==x) return x;
return find(fa[x]);
}
void uni(int x,int y){
x=find(x);
y=find(y);
if(x==y) return;
if(s[x]<s[y]){
fa[x]=y;
s[y]+=s[x];
}else{
fa[y]=x;
s[x]+=s[y];
}
}
void init(int n){
for(int i=1;i<=n;i++){
fa[i]=i;
s[i]=1;
}
}路径压缩 + 按高合并(推荐)
// 5. 路径压缩 + 按高合并
const int MAXN=100000;
int fa[MAXN],h[MAXN];
int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
void uni(int x,int y){
x=find(x);
y=find(y);
if(x==y) return;
if(h[x]<h[y]) fa[x]=y;
else if(h[x]>h[y]) fa[y]=x;
else{
fa[y]=x;
h[x]++;
}
}
void init(int n){
for(int i=1;i<=n;i++){
fa[i]=i;
h[i]=1;
}
}路径压缩 + 按大小合并(推荐)
// 6. 路径压缩 + 按大小合并
const int MAXN=100000;
int fa[MAXN],s[MAXN];
int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
void uni(int x,int y){
x=find(x);
y=find(y);
if(x==y) return;
if(s[x]<s[y]){
fa[x]=y;
s[y]+=s[x];
}else{
fa[y]=x;
s[x]+=s[y];
}
}
void init(int n){
for(int i=1;i<=n;i++){
fa[i]=i;
s[i]=1;
}
}复杂度一览
设总共 $n$ 个元素，$m$ 次操作
| 优化策略组合 | 单次操作均摊复杂度 | 总复杂度 | 说明 |
|---|---|---|---|
| 无优化 | $\mathcal{O}(n)$ | $\mathcal{O}(mn)$ | 最坏情况退化成链结构 |
| 仅路径压缩 | $\mathcal{O}(\log n)$~$\mathcal{O}(n)$ | $\mathcal{O}(m\log n)$ | 不足以避免最坏退化 |
| 仅按秩合并 | $\mathcal{O}(\log n)$ | $\mathcal{O}(m\log n)$ | 合并时尽量避免退化 |
| 路径压缩 + 按秩合并 | $\mathcal{O}(\alpha(n))$ | $\mathcal{O}(m\alpha(n))$ | 几乎常数，推荐 |
| 路径压缩 + 按大小合并 | $\mathcal{O}(\alpha(n))$ | $\mathcal{O}(m\alpha(n))$ | 等价于按秩合并 |
| 按大小合并不加路径压缩 | $\mathcal{O}(\log n)$ | $\mathcal{O}(m\log n)$ | 不推荐单独使用 |
练习
业精于勤，荒于嬉；行成于思，毁于随。