1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
// MOD: Modernizacja Bajtocji [A] | 2024-03-11 | Solution by dkgl
// https://sio2.mimuw.edu.pl/c/pa-2024-1/p/mod/

#include <bits/stdc++.h>

using namespace std;

struct Group {
  bool is_sure = false;
  int repr = -1;
  int height = 1;
  int size = 1;
  inline bool is_surely_not() {
    return !is_sure && size == 1;
  }
  Group(int _repr): repr(_repr) {};
};

int main() {
  #ifndef DKGL_DEBUG
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
  #endif

  int n, q;
  cin >> n >> q;
  vector<int> node_groups(n);
  vector<Group> groups;
  groups.reserve(n);
  for (int i = 0; i < n; ++i) {
    node_groups[i] = groups.size();
    groups.push_back(Group(groups.size()));
  }

  function<int(int)> find_group_repr = [&](int i) {
    if (groups[i].repr == i) return i;
    groups[i].repr = find_group_repr(groups[i].repr);
    return groups[i].repr;
  };

  auto try_union = [&](int node_a, int node_b) {
    int a = find_group_repr(node_groups[node_a]);
    int b = find_group_repr(node_groups[node_b]);
    if (a == b) {
      groups[a].is_sure = true;
      return;
    }
    if (groups[b].height > groups[a].height) swap(a, b);
    groups[a].is_sure |= groups[b].is_sure;
    groups[a].size += groups[b].size;
    groups[b].repr = a;
    if (groups[a].height == groups[b].height) groups[a].height++;
  };

  while (q--) {
    int a;
    char command;
    cin >> command >> a;
    --a;
    switch (command) {
      case '+': {
        int b;
        cin >> b;
        --b;
        try_union(a, b);
        break;
      }
      case '-': {
        auto &group = groups[find_group_repr(node_groups[a])];
        --group.size;
        node_groups[a] = (int) groups.size();
        groups.push_back(Group(groups.size()));
        break;
      }
      case '?': {
        auto &group = groups[find_group_repr(node_groups[a])];
        if (group.is_sure) cout << '1';
        else if (group.is_surely_not()) cout << '0';
        else cout << '?';
        break;
      }
    }
  }

  cout << endl;
  return 0;
}