简介

并查集是一种维护集合的数据结构。

支持合并和查询元素所在集合。

我们将所有元素用点表示，从属关系用边表示，那么每个集合构成了一棵有向树。每个点有且仅有一条出边，指向其父亲。其中根节点的出边指向自己。集合用根节点的编号代表。

实现

初始化

一开始所有的元素指向自己。

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

查询

查找元素所属的集合就是从该元素开始不断跳父亲，直到根节点。

int find(int x){
	return x==fa[x]?x:find(fa[x]);
}

合并

如果要合并 \(x\) 所属集合和 \(y\) 所属的集合，直接将 \(x\) 所属集合的根指向 \(y\) 所属集合的根。

void merge(int x,int y){
	int fx=find(x),fy=find(y);
	fa[fx]=fy;
}

注意到其实不用考虑 \(fx\) 和 \(fy\) 的值是否相同，因为就算相同，根节点的父亲也就是自己。

路径压缩

如果 \(x\) 属于集合 \(u\)，那么查询完后，我们可以直接将所有查询到的节点直接连到根 \(u\) 上。

int find(int x){
	return x==fa[x]?x:fa[x]=find(fa[x]);
}

启发式合并

合并时将较小的集合合并到较大的集合上，这样每次 find 时复杂度就会较低。

void merge(int x,int y){
	int fx=find(x),fy=find(y);
	if(sz[fx]>sz[fy]){
		fa[fy]=fx;
		sz[fx]+=sz[fy];
	}else{
		fa[fx]=fy;
		sz[fy]+=sz[fx];
	}
}

连通性

并查集支持加边维护连通性，每次加边就将两个点所在的联通块集合合并集合。