并查集与ios::sync

作用：1)将两个集合合并

2）询问两个集合是否在一个集合当中

基本原理：每个集合用一颗树来表示。

树根的编号就是整个集合的编号。

每个节点储存它的父节点，p[x]表示x的父节点。

*** 作：1)判断树根：if(p[x]==x)

       2）求x集合编号：while(p[x]!=x) x=p[x];

       3）合并两个集合：找到x的编号p[x],找到y的编号p[y],使p[x]=y;

优化并查集：路径压缩

递归一下:

int find(int x){

       if(p[x]!=x) p[x]=find(p[x]);

//找不到对应的编号（祖宗），就一直递归，知道找到了编号，依次回溯，使每个元素的编号都是祖宗

       return p[x];//返回编号(祖宗)

}

例题:Aclass="superseo">cWing 836

代码：

#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
using namespace std;
const int N=1e5+10;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
ll n,m;
ll p[N];
int find(int x)
{
	if(p[x]!=x) p[x]=find(p[x]);
	return p[x];
}

int main()
{
    IOS;
    cin>>n>>m;
    for(int i=1;i<=n;i++) p[i]=i;
    while(m--)
    {
		char op[2];
		ll a,b;
    	cin>>op>>a>>b;
    	//合并集合 
    	if(op[0]=='M') p[find(a)]=find(b);
    	if(op[0]='Q') 
    	{
    		if(find(a)==find(b)) cout<<"Yes"<