并查集

• 0. 概述
• 1. 数据结构
• 2. 核心函数
  • 2.1. find函数
  • 2.2. join函数
• 3. 模板
• 4. 维护信息的并查集
  • 4.1. 维护各集合中元素总数
  • 4.2. 维护总集合个数
• 5. 完备并查集

0. 概述

• 并查集是用于处理不相交集合的合并与查询的树形数据结构

1. 数据结构

• 准备一个数组用于存储所有点的连通分量（父节点）

const int maxn=2e5+5;
int fa[maxn];

2. 核心函数

2.1. find函数

• 用于查询某个元素的父节点

// 查找元素所在集合的根
int find(int x) {
	// 根节点
	if(x==fa[x]) return x;
//	return find(fa[x]); // 递归查找父节点的父节点
	// 带路径压缩的查找(有效降低递归的时间复杂度)
	// 在返回的路上,顺带修改各节点的父节点为根
	// 这句代码的意思是:fa[x]=find(fa[x]),return fa[x]
	return fa[x]=find(fa[x]);
}

• 带路径压缩的查找和普通查找的区别仅仅在于在递归的过程中把每个子节点的父节点更新为根

2.2. join函数

• 用于连接两个并查集

void join(int a,int b) {
    // b的根作为a的根
    fa[find(a)]=find(b); // b的父节点作为a原本的父节点的父节点
}

3. 模板

题目链接：P3367 【模板】并查集 - 洛谷

• 1）初始化时将每个节点的父节点初始化为自己
• 2）如果 $a$ 和 $b$ 的根相同，则表明二者处于同一并查集中

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+4;
int fa[maxn]; // 记录每个节点的父节点
int find(int x) {
	if(x==fa[x]) 
		return x;
	else
		// 路径压缩
		return fa[x]=find(fa[x]);
}
void join(int l,int r) {
	fa[find(l)]=find(r); // x的父节点的父节点变为y的父节点(合并)
    // 即把l的集合的根节点的父亲设置为r集合的根节点
}
int main() {
	int n,m;
	cin>>n>>m;
	int op,l,r; // op是操作,l和r是合并或判断关系的两个并查集
	// 1. 初始化每个结点的父节点都是自己
	for(int i=1;i<=n;i++) 
		fa[i]=i;
	while(m--) {
		cin>>op>>l>>r;
		if(op==1)
			join(l,r);
		else if(op==2) {
			if(find(l)==find(r)) // 在同一并查集中
				cout<<"Y\n";
			else
				cout<<"N\n";
		}
	}
	return 0;
}

4. 维护信息的并查集

4.1. 维护各集合中元素总数

• 只需要在合并时进行计算即可，将子集合中的元素个数加等到父集合的元素个数中

int cnt[N]; // cnt[i]:以i为根节点的集合的元素个数 

// 维护集合总数的合并
void merge(int a,int b) {
	int x=find(a);
	int y=find(b);
	if(x==y) return;
	fa[x]=y; // a所在集合根节点作为b所在集合根节点的儿子节点
	// 如果遇到重复的语句,那么此时x==y成立,所以不再重复计数
	cnt[y]+=cnt[x];
}

4.2. 维护总集合个数

• 有多少个集合即是看有多少个节点的 $x==fa[x]$ 即有多少个根节点，无需维护，$O(n)$ 遍历一遍即可

5. 完备并查集

• 非常好用

#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: 

const int N=1e5+5;

// 完备并查集
struct DSU {
	// fa:每个结点的父结点
	// p:每个集合的结点数量
	// e:每个集合边的数量
	// f:记录集合中是否存在自环
	vector<int> fa,p,e,f; 

	// 初始化一个并查集
	DSU(int n) {
		// 大小为n+1,下标从0~n,我们可以从1开始使用
		
		fa.resize(n+1); // 大小调整为n+1 
		// fa从起始位置到结束位置,从0开始递增赋值,即父结点为自己
		// 即fa[0]=0,fa[1]=1,...,fa[n]=n
		iota(fa.begin(),fa.end(),0); 
		p.resize(n+1,1); // 每个结点单独成为一个集合,大小为1
		e.resize(n+1); // 初始时每个集合没有边
		f.resize(n+1); // 初始时没有自环
	}
	// 找x所在集合的根节点
	int get(int x) {
		// 找x的根节点,并作路径压缩
		while(x!=fa[x]) {
			x=fa[x]=fa[fa[x]];
		}
		return x;
	}
	// 假设x所在集合为A,假设y所在集合为B,合并A和B
	bool merge(int x,int y) {
		// 设x是y的祖先
		if(x==y) f[get(x)]=1; // 如果自己和自己合并,则存在自环
		x=get(x),y=get(y);
		e[x]++; // 集合A边数+1
		if(x==y) return false;
		if(x<y) swap(x,y); // 指定将编号小的合并到编号大的上
		fa[y]=x; // 集合B父结点变为x
		// 若B有自环,则合并后A有自环,或运算是一起看,有1则1
		// A加上B中边的数量和结点数量
		f[x]|=f[y],p[x]+=p[y],e[x]+=e[y];
		return true;
	}
	// 判断x和y是否在同一集合中
	bool same(int x,int y) {
		return get(x)==get(y);
	}
	// 判断x所在集合是否存在自环
	bool F(int x) {
		return f[get(x)];
	}
	// 输出集合中点的数量
	int size(int x) {
		return p[get(x)];
	}
	// 输出集合中边的数量
	int E(int x) {
		return e[get(x)];
	}
};

int main() {
	// 用完备并查集解板子题
	int n,m;
	cin>>n>>m;
	DSU dsu(n); // 创建并查集
	while(m--) {
		int op,a,b;
		cin>>op;
		if(op==1) {
			cin>>a>>b;
			dsu.merge(a,b); // 合并a,b所在集合
		} else {
			cin>>a>>b;
			if(dsu.same(a,b)) {
				cout<<"Y"<<endl;
			} else {
				cout<<"N"<<endl;
			}
		}
	}	
	return 0;
}

打赏