并查集(保姆级讲解)

文章目录

• 什么是并查集
• • 查找
  • 合并
  • 例题
  • • 代码

什么是并查集

并查集是一种树形的数据结构。
支持两种操作
**查找：**确定某个元素在那个集合
**合并：**将两个集合的元素合并在一起

查找

1.朴素查找

2.优化查找

合并

1.朴素合并


2.优化合并

因为朴素合并的时间复杂度已经是O(1)了，所以一般就不用优化合并了。

例题

链接

代码

#include <bits/stdc++.h>
#define lowbit(x) ((x)&(-x))
#define int long long
#define endl '\n'
#define PII pair<int,int> 
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
int f[10100],a,b,c;
int cha(int x)
{
	if(x==f[x])
	return x;
	else
	return f[x]=cha(f[x]);
}
void he(int x,int y)
{
	f[cha(x)]=cha(y);
 } 
signed main()
{
	IOS
	int m,n;
	cin>>m>>n;
	for(int i=1;i<=m;i++)
	f[i]=i;
	for(int i=1;i<=n;i++)
	{
		cin>>a>>b>>c;
		if(a==1)
		{
			he(b,c); 
		}
		else
		{
			int x=cha(b),y=cha(c);
			if(x==y)
			cout<<'Y'<<endl;
			else
			cout<<'N'<<endl; 
		}
	}
	return 0;
}