并查集

并查集支持的操作：

1. 将两个集合合并

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

3. 基本原理：每一棵树用树根来表示，树根的编号就是整个集合的编号。每个节点储存它的父节点，p[x]表示x的。父节点。

4. 问题一： 如何判断树根？当p[x] == x时，p[x]为根节点。

5. 问题二：如何求x的集合编号？while(p[x]!=x)x = p[x];最后的x即为x的集合编号

6. 如何合并两个集合？答：假设py是y的集合编号， px 是x的集合编号，p[x] = y

并查集模板

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int p[N];
int find(int x)//返回x的祖宗节点 + 路径压缩
{
    if(p[x]!=x) p[x] = find(p[x]);
    return p[x];
}
int main()
{
    int n,m;
    cin >> n >>m;
    for(int i = 1; i <= n; i ++)p[i] = i;
    while(m --)
    {
        char op;
        int a, b;
       cin >>op;
        if(op =='Q')
        {
            cin >>a >>b;
            if(find(p[a]) != find(p[b]))cout <<"No"<<endl;
            else cout << "Yes"<<endl;
        }
        else {
            cin >>a >>b;
            p[find(a)] = find(b);//让a的祖宗节点的父节点等于b的祖宗节点
        }
    }
}