并查集入门(水)

huangzelin 2023-07-18 17:56:50 2023-11-15 22:06:00 36

注:本贴仅用于记录我自己对于并查集的一些粗略理解,方便以后重新回忆

注:如果本帖对你有帮助,那并不是我的本意(笑

注:本贴会跟随我对并查集的深入学习不断更新

注:本文默认读者拥有一些并查集基础

注:文字量过大,可能引起不适,但是理解后会有醍醐灌顶的效果

并查集是我很喜欢的一个算法,它小巧优美,味道鲜美,入口即化……(误


|不按照难度排版

一、并查集
  • 初始化

  • 查询

  • 合并

  • 优化(路径压缩和按秩合并)

二、扩展域并查集和带权并查集
  • 扩展域并查集

  • 带权并查集

三、并查集与图论入门
  • 最小生成树

  • 判环

  • 点是相交线的交集

四、维护更多信息
  • 集合内的元素数量

  • 深度(按秩合并)

  • 那年岁月

五、并查集的填充应用
  • 单点填充

  • 多点填充

  • 树上染色问题

  • map+并查集

六、可持久化并查集
  • 模板

一、并查集

并查集通常使用在一些有N个元素的集合应用问题中,刚开始让每个元素构成一个单元素的集合,然后对其进行合并和查询操作

模板题:https://wikioi.cn/problem/518

我们可以开一个数组f(father的缩写),指向当前元素的父节点,刚开始

如果f[i]表示i的父节点,那么我们会发现并查集的图其实是一个森林(由很多棵树组成的图)

那么想知道两个点在不在同一个集合,就只需要判断它们的祖先是不是同一个

我们用 来寻找x的祖先:

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

如果 那么x和y就在同一个集合

合并两个元素所在的集合,其实就是合并两棵树,那么我们只需要把x的祖先变成y的祖先的儿子就行了

    int fx=find(x),fy=find(y);
    if(fx!=fy) f[fx]=fy;

如果仅仅只是这样,那么恭喜你,你T了

因为到此为止,查询的时间复杂度是O(d) ,d是查询点的深度,合并因为需要查询,所以也是O(d)

我们不得不想出一些办法来优化

这应该是极其常用的一种压缩办法,而且很方便

因为我们查询所需要的只是当前点的祖先,至于它的父亲是谁

Who care?

所以我们希望f[x]指向的是x的祖先,而不是他的父亲

那么这里就有一个神操作了,我们可以把find函数改为:

int find(int x){
    if(f[x]==x) return x;
    return f[x]=find(f[x]);   //区别在这里
}

这样一来,x到它祖先这条路径上所有的点的父亲f[x]就变成了它们的祖先

整个算法的时间复杂度就变得有些玄学,但据说是O(n),大差不差就是这样吧

路径压缩的在压缩的同时也破坏了树的形状,所以并不适用于一些场合,比如可持久化并查集

不过也不用担心,大部分情况下还是够用的,你可以需要用到的时候再回来看

按秩合并,我们在维护f[x]的同时,还需要维护一个rank数组,即树高

注:树高只用使用按秩合并的情况下才可以维护

:rank[i]=1;

:同第2条的查询,不需要让f[x]指向祖先

:我们让树高更小的树接在较高的树上,这样就可以保证

    int fx=find(x),fy=find(y);
    if(fx!=fy) {
        if(rank[fx]>rank[fy]) swap(fx,fy); //将fx接在fy上
        f[fx]=fy;
        rank[fy]=max(rank[fy],rank[fx]+1);
    }

已知查询速度和深度有关,这样就保证了每次查询的时间复杂度为 (似乎是没有路径压缩快的)


二、扩展域并查集和带权并查集

这是一个很巧妙的概念,但是上手比较恶心(我智商太低了)

我只是提出来让大家知道有这么一个概念(不然扩展域并查集要生气了),并不打算细讲

理由如下:

① 实用性太差

② 考虑情况比较恶心

③ 可以用带权并查集解决(这个后面解释),而且它的实用性非常强

粗略提一下,其实就是将f[n]扩展到f[kn]来存储更多关系

如果你感兴趣的话可以去了解一下,因为情况下扩展域并查集比带权并查集快

我超喜欢这个算法,当时在网上找文章看,有些写得真的很烂,导致我前几篇都没看懂(我太蠢了)

我自认为自己的理解方式非常丝滑

如何理解带权并查集:

初看这个概念可能会被吓到,因为它看起来有点难,但其实很简单

我们只是在维护父子关系的同时维护而已

这么做有什么好处?

假设我们有n个带权值点,第i个点的权值是q[i],每次告诉你q[x]和q[y]的差值为k或者询问你q[x]和q[y]的差是多少

很棘手是吧,但如果这是一个数学问题

告诉你 a-b=x,a-c=y,问你b-c是多少,你很快就能得到正确答案

那么放在计算机上呢?

如果我们将a同时作为b和c的祖先,因为我们分别知道 b和a,c和a的关系,是不是就可以求出b和c的关系了?

就像路径压缩中我们希望f[x]表示x的祖先,我们现在新开一个数组w,我们也希望w[x]表示x和它祖先的关系

这样我们就可以算出集合内任意两元素的关系了

(给你一点时间理解一下)

//此时i就是自己的祖先,q[i]与q[i]的差是0

int find(int x){
    if(f[x]==x) return x;
    int fx=find(f[x]);    //先保留x和它父亲的关系,fx存储x的祖先
*   w[x]+=w[f[x]];        //此时w[x]表示q[x]-q[f[x]],w[f[x]]表示q[f[x]]-q[fx],两者相加使得w[x]成为x和祖先的关系
    return f[x]=fx;
}

(再给你一点时间理解一下)

!!!重磅推出我的神技:向量理解法!!!

如果a的父亲是b,祖先是c,那么在*处

请你仔细理解这个概念,因为接下来我们要开挂了!

:将fx合并到fy,在 的基础上,我们还需要改变 的值

也就是求出

我们已知的是

q[x]-q[y]

已知

得到公式:

如果画图推导的话你可能会死(确信)

同样我们给出代码:

    int fx=find(x),fy=find(y);
    if(fx!=fy){
		f[fx]=fy;
		w[fx]=w[y]+k-w[x];
    }

等等,我们的问题还没有解决呢

按照题目,它将要询问

即为

如果不在同一个集合,那就没办法运算,反之

因为

所以

OVER!可以去杀题了

https://wikioi.cn/problem/1202

https://wikioi.cn/problem/4500

https://wikioi.cn/problem/4690 //这些是用带权并查集的题目

https://wikioi.cn/problem/10071

https://wikioi.cn/problem/10479 //这些是可以用扩展域并查集,但我建议用带权并查集的题目

为什么带权并查集可以代替扩展域并查集

数组大小为 kN 的扩展域并查集通常用于维护N个元素的k组关系(敌人,同伴……)

如果我们分别知道 a和b,a和c的关系,那么我们就可以推出 b和c的关系,在带权并查集中可以通过一个%k的操作来实现


三、并查集与图论入门

最小生成树的算法之一 : Kruskal 便是以并查集为基础的 (另外比较常用的算法还有prim算法)

其中 Kruskal 算法多用于稀疏图

模板题 https://wikioi.cn/problem/551

先将所有边按照从小到大排序,然后检索过去,能连就连

这个检索的过程需要用到并查集,判断两个点是否已经联通,如果不连通就加入同一个集合

当连接到n-1条边的时候,最小生成树就建成了

最大生成树也是这样,排序的时候需要从大到小排序

在无向图中,不断合并连通块,如果发现两点已经在同一个集合中,则说明有环

无向图也可以使用这种方法判环,但需要满足每个点的出度小于等于1

其实我感觉并查集判环没有什么优势

线

直接上题目:

给定一张n*m的01矩阵,1表示此处埋有地雷

如果(x1,y1),(x1,y2),(x2,y1)都埋有地雷,那么请在(x2,y2)也埋一颗地雷

请输出埋好所有地雷后的01矩阵

举个例子:

4 5
1 0 1 0 0
0 0 0 0 0
1 0 0 0 1
0 0 1 0 0

1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
1 0 1 0 1

这道题看似棘手,其实用并查集的思路很快就能解决

首先将每一行作为一个元素放入f[i],再将每一列作为一个元素放入f[i+n]

如果(x,y)上有地雷,那么第x行和第y列就相交产生了一个点,我们可以将这两条线加入同一个集合

即把x和y+n合并

最后再枚举一边,对于每个点(a,b),如果a和b+n在同一个集合中,那么这个点上有地雷

没有找到这种题目,等我找到了再放进来吧

d=====( ̄▽ ̄*)b


四、维护更多信息

可以使用sum数组来存储元素的数量,初始值为1

只需要改变一下合并就行了:

    int fx=find(x),fy=find(y);
    if(fx!=fy){
		f[fx]=fy;
		sum[fy]+=sum[fx];
    }

因为后面不再使用到sum[fx],所以不用清零

储存深度的前提是使用按秩合并,路径压缩中的深度没有意义

这里只需要改变find函数即可(deep数组存储点的深度)

int find(int x){
	if(f[x]==x) return x;
	int fx=find(f[x]);
	deep[x]=deep[f[x]]+1;
	return fx;
}

是不是和带权并查集有点像?

但是很遗憾,这不是。虽然深度也属于点和根的关系,但带权并查集强调的是点和根的权值关系,深度并不是权值。

H市有n个企业,每年都有两个企业合并,直到只剩下1个企业

年终的的时候,同一个企业的人会聚集起来

“嘿,你最开始是哪个企业的?”

“我是愤怒美人鱼暴打搁浅海盗船企业的,你呢?”

“我是疯狂星期四没牙老奶奶狂炫全家桶企业的。”

“那我们第一次见面是什么时候?”

“那年是……”

这个问题把两人问住了,他们都是公司的高管,现在是你表现的机会了:

整理一下问题,你需要查询两个元素被合并到一个集合的时间。

这是记录在边上的数值,显然不能使用路径压缩了,不然边就没了。

当然给边赋值比较困难,因为一条边对应一个儿子节点,我们可以把时间记录在儿子节点上。

用t数组存储时间,year表示当前是第几年。

改变合并:

    int fx=find(x),fy=find(y);
    if(fx!=fy){
		f[fx]=fy;
		t[fx]=year;
    }

接下来是查询,我们需要找到两个集合合并到的根结点,这是什么?

最近公共祖先啊!

因为,所以只需要不断上移x和y中深度更大的点,最后一定会相同

什么?你问deep怎么求?请上移至谢谢 ¯_(ツ)_/¯

然后看一下查询的代码(这里和普通的LCA不同,只需要枚举到最近公共祖先前一位即可)

int LCA(int x,int y){
    if(find(x)!=find(y)) return 0;
    int ans = 0;
    while(x!=y){
		if(deep[x]<deep[y]) swap(x, y);
		ans=max(ans,t[x]),x=f[x];
    }
    return ans;
}

第一个问题解决了,两个高层还在继续攀谈:

“那么那年年终我们企业是由多少个小企业组成的?”

“那年是……”

你同样将这个问题秒杀了,只需要再维护一个元素个数sum

查找x和y的最近公共祖先f,输出sum[f]即可

我相信这对你来说不是什么难事(如果是,请返回第三章第4节重修)

https://wikioi.cn/problem/4668 快去把这题秒了把

可以证明,合并后新树的直径两端必然为原两树共四个直径端点中的两个


五、并查集的填充应用

有n个石头横向排布在地上,他们的编号分别是1,2,3,……,n-1,n

接下来给出m个操作,每次给出两个值l和r,你需要把位置编号l-r中最大的石头丢掉(如果有的话),每个石头只能丢1次

这道题目暴力大家都会打,时间复杂度O(n^2),显然不是我们想要的

我们希望的是在O(1)的时间内找到我们要丢掉的石头,所以我们定义f[i]表示i之前第一个石头的位置

初始状态:f[i]=i

是不是熟悉起来了?

合并:如果把第f[i]个石头丢掉,那么下一个要丢的石头就变成了f[f[i]-1]

所以

然后你恍然大悟,这不就是并查集吗?

每个集合就是一段连续已丢的石头,根节点就是这一段石头前面那个没丢的石头

如果把那个石头丢了,就要将这个集合并入前一个集合

优化的就不讲了,两种都可以

然后我们来扩展一下:

1.如果丢的最小的石头怎么做?

2.如果这不是n个石头,而是n个石头堆,每堆石头有ai堆石头怎么办?

3.如果我们每次丢bi个石头怎么办?

4.如果将2、3一起考虑怎么办?

1和2应该比较好解决(其实3和4也很好解决

如果你会23,那么4也就会了,那我们来解决3

核心代码:

scanf("%d%d%d",&l,&r,&b);
int j=find(r);
while(b--){
	if(j<l) break;
	f[j]=find(j-1);
}

短小精悍,不是么?

例题: https://www.luogu.com.cn/problem/AT_past202010_m

偶然做到的题目,正解似乎是树链剖分,但我用并查集拿到了最优解

使用LCA将染色路径分成两条链,对他们分别进行染色即可

唯一不同的就是原来是指向左/右位置,现在是指向父节点,其它基本一致

例题:https://www.luogu.com.cn/problem/AT_abc214_e

本来是单点填充的模板,可惜数据达到了

所以我们可以开一个map数组,要用到的时候再建立一个父亲结点

	int fx=t[i].r;
	if(f.count(t[i].r)) fx=find(t[i].r);
	if(fx<t[i].l) continue;
	if(!f.count(fx-1)) f[fx-1]=fx-1;
	f[fx]=find(fx-1);

六、可持久化并查集

毒瘤数据结构

本质上是将数组可持久化,我目前还没有做到需要用到这种算法的题目,所以也不知道有什么用,暂时先把模板放在这里吧

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int M=300010;
struct hh{
	int l,r;
	int f,h;
}t[M*40];
int n,m;
int rt[M],top;
int build(int l,int r){
	int s=++top;
	if(l==r){
		t[s].f=l;
		t[s].h=1;
		return s;
	}
	int mid=(l+r)/2;
	t[s].l=build(l,mid);
	t[s].r=build(mid+1,r);
	return s;
}
int find_place(int s,int l,int r,int x){
	if(l==r) return s;
	int mid=(l+r)/2;
	if(mid>=x) return find_place(t[s].l,l,mid,x);
	else return find_place(t[s].r,mid+1,r,x);
}
int find(int s,int x){
	int sx=find_place(rt[s],1,n,x);
	if(t[sx].f==x) return sx;
	return find(s,t[sx].f);
}
bool sc_find(int s,int x,int y){
	int fx=find(s,x),fy=find(s,y);
	return (t[fx].f==t[fy].f);
}
int clone(int s){
	t[++top]=t[s];
	return top;
}
int find_new(int u,int l,int r,int x,int f){
	int s=clone(u);
	if(l==r) {
		t[s].f=f;
		return s;
	}
	int mid=(l+r)/2;
	if(mid>=x) t[s].l=find_new(t[s].l,l,mid,x,f);
	else t[s].r=find_new(t[s].r,mid+1,r,x,f);
	return s;
}
int do_h(int u,int l,int r,int x,int h){
	int s=clone(u);
	if(l==r) {
		t[s].h=max(t[s].h,h+1);
		return s;
	}
	int mid=(l+r)/2;
	if(mid>=x) t[s].l=do_h(t[s].l,l,mid,x,h);
	else t[s].r=do_h(t[s].r,mid+1,r,x,h);
	return s;
}
void merge(int s,int x,int y){
	int fx=find(s,x);
	int fy=find(s,y);
	if(t[fx].f==t[fy].f) return;
	if(t[fx].h>t[fy].h) swap(fx,fy);
	rt[s]=find_new(rt[s],1,n,t[fx].f,t[fy].f);
	rt[s]=do_h(rt[s],1,n,t[fy].f,t[fx].h);
}
int main(){
	cin>>n>>m;
	rt[0]=build(1,n);
	for(int i=1;i<=m;++i){
		int p,a,b;
		scanf("%d%d",&p,&a);
		if(p==1){
			scanf("%d",&b);
			rt[i]=rt[i-1];
			merge(i,a,b);
		}
		if(p==2) rt[i]=rt[a];
		if(p==3){
			scanf("%d",&b);
			printf("%d\n",sc_find(i-1,a,b));
			rt[i]=rt[i-1];
		}
	}
	return 0;
}
{{ vote && vote.total.up }}