【acwing】837. Number of connected block points

subject

Ideas

use size[] Store the number of each root node

Code

// The number of points in a connected block exists in the root node 

#include<iostream>
using namespace std;

const int N=100005;
int siz[N];  // Store the number of points in the connected block 
int p[N];    // Store the parent node 
int n,m;

int find(int x){
      // Find the root node + Path optimization 
    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;
        siz[i]=1;  // Note that there siz[i] The initial values of are 1, instead of i
    }
    
    while (m -- ){
    
        string op;
        int x,y;
        cin>>op;
        
        if(op[0]=='C'){
    
            cin>>x>>y;
            if(find(x)==find(y)){
     // If x,y It's already connected , Then there is no need to go down 
                continue;
            }
            
            siz[find(y)]+=siz[find(x)];// The number of each connected block exists in its root node ,y The number of trees is y+x（x For the trees connected ）
                                
            p[find(x)]=find(y);  // This sentence should be in siz[find(y)]+=siz[find(x)] After this sentence , Otherwise x and y The value of the root node will change 
            
        }else if(op[1]=='1'){
    
            cin>>x>>y;
            if(find(x)==find(y)){
      // The root node is the same , Explain in a connected block 
                cout<<"Yes"<<endl;
            }else{
    
                cout<<"No"<<endl;
            }
        }else{
    
            cin>>y;
            cout<<siz[find(y)]<<endl;  // Directly return the root node of the current point size[]
        }

    }
    
    return 0;
}