并查集入门（水）

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

注：如果本帖对你有帮助，那并不是我的本意（笑

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

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

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

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

|不按照难度排版

一、并查集

• 初始化

• 查询

• 合并

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

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

• 扩展域并查集

• 带权并查集

三、并查集与图论入门

• 最小生成树

• 判环

• 点是相交线的交集

四、维护更多信息

• 集合内的元素数量

• 深度(按秩合并)

• 那年岁月

五、并查集的填充应用

• 单点填充

• 多点填充

• 树上染色问题

• 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;
}