For example, the following queries can be handled with a Disjoint Set Union (DSU).

• Type \(a\): add an undirected edge between vertices \(u\) and \(v\).
• Type \(b\): determine if vertex \(v\) is reachable from vertex \(u\) via edges.

Can we solve the original problem with DSU as well?

It is sufficient to maintain the following value for each connected component:

• the number of black vertices contained in the connected component.

Based on this information, type-\(3\) queries can be answered by checking if that connected component contains at least one black vertex.

Sample code (C++):

#include<bits/stdc++.h>
#include<atcoder/dsu>

using namespace std;
using namespace atcoder;

int main(){
  int n,q;
  cin >> n >> q;
  dsu d(n+1);
  vector<int> c(n+1,0);
  vector<int> s(n+1,0);

  while(q--){
    int typ;
    cin >> typ;
    if(typ==1){
      int u,v;
      cin >> u >> v;
      u=d.leader(u);
      v=d.leader(v);
      if(u!=v){
        d.merge(u,v);
        int w=d.leader(u);
        s[w]=s[u]+s[v];
        s[u^v^w]=0;
      }
    }
    else if(typ==2){
      int u;
      cin >> u;
      s[d.leader(u)]-=c[u];
      c[u]^=1;
      s[d.leader(u)]+=c[u];
    }
    else{
      int u;
      cin >> u;
      if(s[d.leader(u)]){cout << "Yes\n";}
      else{cout << "No\n";}
    }
  }
  return 0;
}