decodeX_it_is's blog

By decodeX_it_is, history, 9 months ago, In English

My approach is while creating edge if anyone having black colour tranfer it to parent and while changing colour means query 2 just change colour of parent ,,, Problem

class DSU{
    public:
    vector<int>par;
    vector<pair<int,int>>rnk;
    // 0->white,1->black 
    DSU(int n){
        par.resize(n+1);
        rnk.assign(n+1,{1,0});
        for(int i=1;i<=n;i++)par[i]=i;
    }

    int find_pita(int src){
        if(src==par[src]) return src;
        return par[src]=find_pita(par[src]);
    }

    void take_union(int a,int b){
        a=find_pita(a),b=find_pita(b);
        if(a==b)return ;
        if(rnk[a].first>rnk[b].first){
            rnk[a].first+=rnk[b].first;
            par[b]=a;
            if(rnk[b].second==1)rnk[a].second=1;
        }else{
            rnk[b].first+=rnk[a].first;
            par[a]=b;
            if(rnk[a].second==1)rnk[b].second=1;
        }
    }
    void flip_col(int src){
        int u=find_pita(src);
        rnk[u].second=!rnk[u].second;
    }
};
void coderaryan() {
    // executing code from here 
    int t=1;
    while (t--) {
        int n,q;
        cin >> n>>q;
        DSU vab(n);
        while(q--){
           1  int x;cin>>x;
            if(x==1){
                int u,v;cin>>u>>v;
                vab.take_union(u,v);
            }else if(x==2){
                int u;cin>>u;
                vab.flip_col(u);
            }else{
                int u;cin>>u;
                u=vab.find_pita(u);
                vab.rnk[u].second==1?cout<<"Yes"<<endl:cout<<"No"<<endl;
            }
        }
    }
}

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it