C++ 代码

#include<iostream>
using namespace std;
const int N=1e5+10;
int p[N],n,m;//这里的p[N]是是父节点的集合
int find(int x)
{
    //这里直接把父节点等于祖宗节点了 即路径优化
    if(p[x]!=x)p[x]=find(p[x]);//只有第一次找的时候需要一个一个的找父节点 然后找祖宗节点 第二次找的时候就直接把路径上的 找过的省略了路径 这里就是指路径压缩 也就是递归优化 减少了递归的次数
    return p[x];//这里只有当父节点等于本身的时候就是找到了祖宗节点 
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)p[i]=i;//第一次每个元素 是一个集合
    while(m--)
    {
        string op;
        cin>>op;
        int a,b;
        if(op=="M"){cin>>a>>b;p[find(a)]=find(b);}//合并即 让一个节点的祖宗节点 的 父节点等于 另一个节点的祖宗节点
        else if(op=="Q"){cin>>a>>b;if(find(a)==find(b))cout<<"Yes"<<endl;else cout<<"No"<<endl;}
    }
    return 0;
}