情况

便于处理多个集的合并，区分。

原理

在每次查询时都进行优化：每次查询时都把存节点位置更新为当前最高父节点。
当①为父节点，②指向①，③指向②，那么查询一次③的父节点操作时，③就更新为指向①。
最后总是保证在同一个集合内，指向的节点都为同一个。

代码

#include <iostream>

using namespace std;

const int N = 100010;

int p[N];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);    //查询最终父节点
    return p[x];    //每次返回上一个节点的父节点
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    while (m -- )
    {
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        if (*op == 'M') p[find(a)] = find(b);    //合并操作，同时更新父节点
        else
        {
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }

    return 0;
}

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/45287/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。