Submission #68777956

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

struct DSU {
  vector<int> par, sz, black;
  int k;

  DSU(int n) : par(n + 1), sz(n + 1, 1), black(n + 1, 0) {
    k = n;
    for (int i = 1; i <= n; ++i) par[i] = i;
  }

  int find(int i) {
    if (par[i] == i) return i;
    return par[i] = find(par[i]);
  }

  bool same(int i, int j) {
    return find(i) == find(j);
  }

  int get_size(int i) {
    return sz[find(i)];
  }

  int count() {
    return k;
  }

  void join(int i, int j) {
    i = find(i);
    j = find(j);
    if (i != j) {
      k--;
      if (sz[i] < sz[j]) swap(i, j);
      par[j] = i;
      sz[i] += sz[j];
      black[i] += black[j];
    }
  }

  void add(int v) {
    v = find(v);
    black[v]++;
  }

  void rem(int v) {
    v = find(v);
    black[v]--;
  }

  bool has(int v) {
    v = find(v);
    return black[v] > 0;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, q;
  cin >> n >> q;

  DSU dsu(n);
  vector<int> color(n + 1, 0);

  while (q--) {
    int ty;
    cin >> ty;
    if (ty == 1) {
      int u, v;
      cin >> u >> v;
      dsu.join(u, v);
    } 
    else if (ty == 2) {
      int v;
      cin >> v;
      if (color[v] == 0) {
        color[v] = 1;
        dsu.add(v);
      } 
      else {
        color[v] = 0;
        dsu.rem(v);
      }
    } 
    else {
      int v;
      cin >> v;
      cout << (dsu.has(v) ? "Yes\n" : "No\n");
    }
  }

  return 0;
}

Submission Info

Judge Result