并查集模板

并查集(Union(并),Find(查),Set(集))

一般用树的形式保存集合,但是是用数组模拟的树


对于并查集树上的所有点,只有根结点是p[x]=x的,其他的p[x]都是父结点

那么就可以通过while(p[x]!=x)x=p[x];来查询一个点的编号,属于哪个集合

询问两个元素是否在同一个集合中,直接查询两个元素的编号是否相同即可

合并两个集合:直接让一个集合树直接插到另一个集合树的某个结点即可,这样就实现了集合合并(同一个编号根节点)

对于while(p[x]!=x)x=p[x];的优化:
首先通过while(p[x]!=x)x=p[x];去找到根节点,现在是只有一条路径
找到根节点后,直接把一路上找的所有祖先点都直接连上根结点
这样一条长路径就变成长度为1的路径了
这样的操作叫做路径压缩,寻找每个点的编号的效率也就大大提高了,接近O(1)

#include<iostream>

using namespace std;

const int N = 100010;

int n,m;
int p[N];//元素父节点

//最核心操作
int find(int x)//返回x祖宗结点 + 路径压缩
{
	if(p[x] != x)p[x]=find(p[x]);//p[x]不是根结点,就让p[x]=祖宗结点(即find(p[x])
	return p[x];//压缩 
}

int main()
{
	cin >> n >> m;
	//初始时每一个元素是单独一个集合
	//每一个集合只有一个点,集合的树根就是自己
	//当p[x]=x的时候,x就为树根
	for(int i=1;i<=n;i++)p[i]=i;
	
	while(m -- )
	{
		string op;
		int a,b;
		cin >> op >> a >> b;
		if( op == "M") p[find(a)] = find(b);//find(a)为a的祖宗结点,设置a所在的集合树 接上b集合的根结点
		else
		{
			if(find(a) == find(b))cout << "Yes" << endl;
			else cout << "No" << endl;
		}
	}
	
	return 0;
}