【算法】无趣的并查集

并查集

---

定义

把许多有关系的人合并成一个集合
然后询问其中的人是否有关系的时候用并查集

---

思路

用树存图
每一次输入判断他们的祖先是否同一个
不同的话就把两个数的祖先改成同一个
最后的询问只要O（1）

---

例子和代码

一个入门的并查集题目

洛谷P1551:https://www.luogu.org/problemnew/show/P1551

代码：

#include<iostream>
using namespace std;
int father[5001];
int n,m,p;
int find(int x)
{
	if(father[x]!=x)//路径压缩优化
	father[x]=find(father[x]);//把路上的所有点祖先全部改掉
	return father[x];
}
void unionn(int x,int y)
{
	father[y]=x;//y的祖先为x的祖先
	            //相当于合并祖先
}
int main()
{
	cin>>n>>m>>p;
	for(int i=1;i<=n;i++)
	{
		father[i]=i;//所有数据初始祖先为自己
		            //独立的一个数为一个集合
	}
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		int r1,r2;
		r1=find(x);
		r2=find(y);//寻找两个数的祖先
		if(r1!=r2)//如果不是同一个祖先
		{
			unionn(r1,r2);//合并
		}
	}
	for(int i=1;i<=p;i++)
	{
		int x,y;
		cin>>x>>y;
		if(find(x)==find(y))//如果是同一个祖先
		{
			cout<<"Yes"<<endl;//是
		}
		else
		cout<<"No"<<endl;//否
	}
	
}