并查集

注意路径压缩以及字符串录入部分技巧。

模板函数

初始化

void init(){
    for(long long int i=0;i<1e6;i++){
        fa[i]=i;
    }
}

⭐⭐查询

int find(int i){
    //压缩路径,节省时间
    if(fa[i]!=i){
        fa[i]=find(fa[i]);
    }
    return fa[i];
}

有时会超时

int find(int i){
    if(fa[i]==i) return i;
    return find(fa[i]);

}

⭐⭐合并（常写）

void merge(int i,int j){
    fa[find(i)]=find(j);
}

C++ 代码

#include <iostream>

using namespace std;

int const N=1e6;

int fa[N];

void init(){
    for(long long int i=0;i<1e6;i++){
        fa[i]=i;
    }
}

int find(int i){
    /*if(fa[i]==i) return i;
    return find(fa[i]);*/

    //压缩路径,节省时间

    if(fa[i]!=i){
        fa[i]=find(fa[i]);
    }
    return fa[i];
}


void merge(int i,int j){
    if(find(i)==find(j)) return;

    fa[find(i)]=find(j);

}


int main(){
    init();

    int n,m;
    scanf("%d%d",&n,&m);
    while(m--){
        int a,b;
        char op[2];
        scanf("%s%d%d",op,&a,&b);  //录入技巧
        if(op[0]=='M'){
            merge(a,b);
        }
        else{
            if(find(a)==find(b)) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }


    return 0;
}