【数据结构】并查集

• 主要内容：并查集

介绍

用于（近乎$O(1)$）快速地：

1. 将两个集合合并
2. 询问两个元素是否在一个集合当中

基本原理：

• 每个集合用一颗树维护，每棵树的根节点的编号即当前集合的编号
• 对于每个点，都存储它的父节点是谁 ：p[x]表示x的父节点
• 当要找某个点是否属于某个集合时，就往上找到根节点

如何判断树根：

• if(p[x]==x)

如何求x的集合编号

• while(p[x]!=x) x=p[x];
• 复杂度优化（路径压缩）：当x往上找的时候，一旦找到根节点，就把这条路径上的所有节点的父节点都指向根节点；基本上就能看成O（1）

如何合并两个集合

• p[x]是x的集合编号，p[y]是y的集合编号：p[x]=y

---

AcWing836 合并集合（模板题）

题意

进行 m个操作，操作有两种：

1. M a b，将编号为 a和 b的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
2. Q a b，询问编号为 a和 b 的两个数是否在同一个集合中；

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
int p[N];//p[i]:编号为i的节点的父节点 

//关键方法find：返回x所在集合的编号（祖宗节点）+路径压缩 
int find(int x){
	//如果x不是祖宗节点的话，就让它的父节点=它父节点的祖宗节点：往上递归
	if(p[x]!=x) p[x]=find(p[x]); 
	return p[x];
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) p[i]=i;//初始化 
	while(m--){
		char op;int a,b;cin>>op>>a>>b;
		if(op=='M') p[find(a)]=find(b); //合并两个集合
		else{
			if(find(a)==find(b)) cout<<"Yes"<<endl;
			else cout<<"No"<<endl;
		}
	}
}

---

AcWing837 连通块中点的数量

题意

给定一个包含 n个点（编号为 1∼n1∼n）的无向图，初始时图中没有边。

进行 m 个操作，操作共有三种：

1. C a b，在点 a 和点 b间连一条边，a和 b 可能相等；
2. Q1 a b，询问点 a 和点 b 是否在同一个连通块中，a和 b可能相等；
3. Q2 a，询问点 a 所在连通块中点的数量；

思路

• 两个点之间连一条边==合并两个集合；
• 只是多了一个统计集合中点的数量的操作而已

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
int p[N],cnt[N];
//cnt[i]表示的是 根节点i 所在集合的大小 
int find(int x){
	if(p[x]!=x) p[x]=find(p[x]);
	return p[x];
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		p[i]=i;
		cnt[i]=1;
	} //初始化 
	while(m--){
		string op;int a,b;cin>>op;
		if(op=="C"){
			cin>>a>>b;
			if(find(a)==find(b)) continue;
			//下面这两行顺便别颠倒了 
			cnt[find(b)]+=cnt[find(a)]; 
			p[find(a)]=find(b);
		}
		else if(op=="Q1"){
			cin>>a>>b;
			if(find(a)==find(b)) cout<<"Yes"<<endl;
			else cout<<"No"<<endl;
		}else{
			cin>>a;
			cout<<cnt[find(a)]<<endl;
		}
	}
}