Can you help me in this DSU problem asked at Atcoder E??

Правка en1, от decodeX_it_is, 2025-08-27 01:45:34

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;
            }
        }
    }
}
Теги atcoder beginner

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский decodeX_it_is 2025-08-27 01:45:34 1751 Initial revision (published)