并查集（c++数组实现）

作用：

将两个集合合并(将其中一个集合的根赋值给另一个集合的根做另一个集合的根的儿子)询问两个元素是否在一个集合中(判断两个元素的根是否相同)

原理：

每个集合用一个树来表示。树根的编号就是整个集合的编号。每个节点存储它的父节点，p[x]表示x的父节点。

问题一：如何判断树根：if(p[x] == x)

问题二：如何求x的集合编号：while(p[x] != x) x = p[x];

问题三：如何合并两个集合：px是x的集合编号，py是y的集合编号。p[x] = y;

优化

路径压缩：每次找到一个元素将这个元素直接指向根节点，第二次查的时候就很快可以查到。

核心代码：

int find(int x)//返回x的祖宗节点 + 路径压缩！
{
    if(p[x] != x) p[x] = find(p[x]);//注意:这里的下标存的是实际值，下标所对应的值才是节点地址。！！！！！
    return p[x];
}

例：acwing-836-合并集合

[acwing-合并集合](836. 合并集合 - AcWing题库)

上图画圈的地方代表父节点！

#include
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 m,n;
    cin>>n>>m;
    for(int i=1;i<=n;i++) p[i] = i;
    while(m--)
    {
        char s;
        int a,b;
        cin>>s>>a>>b;
        if(s == 'M') p[find(a)] = find(b);
        else
        {
            if(find(a) == find(b)) cout<<"Yes"<