【acwing】836. Merge sets

subject

analysis

A very classic template question of joint search set

Code

#include<iostream>

using namespace std;

const int N=100005;

int p[N];//P[N] The value of is stored as N The parent node of this number 

int find(int x){
       // return x The ancestor node of + Path compression 
    if(x!=p[x]){
       // If x There is no root node , Then go straight up , And make each point finally point to the root node 
        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; // Let the parent node of all numbers point to itself 
    }
    
    while(m--){
    
        string op;
        int a,b;
        cin>>op>>a>>b;
        if(op[0]=='M'){
     // Merge sets 
            p[find(a)]=find(b); //a The parent node of the root node of =b The following nodes of , hold a As b A subtree of 
            
        }else{
     // Query operation 
            if(find(a)==find(b)){
      // If a The root node and b The root nodes of are equal , Then it belongs to the same set 
                cout<<"Yes"<<endl;
            }else{
    
                cout<<"No"<<endl;
            }
        }
    }
    return 0;
}