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
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
// UWAGA: implementacja disjoint-set / find-union mocno bazuje na https://pl.wikipedia.org/wiki/Struktura_zbior%C3%B3w_roz%C5%82%C4%85cznych

#include <cstdio>
#include <functional>

using namespace std;

int n, q, i, a, b, next_set_id, next_real_id;
char operation;
int parent[1300001], node_to_set_id[1300001], set_rank[1300001], set_computers_number[1300001], set_type[1300001], real_id[300001], reverse_real_id[1300001];

void new_set_single(int x) {
  // printf("! new_set_single %d\n", x);
  parent[x] = -1;
  node_to_set_id[x] = next_set_id;
  set_rank[next_set_id] = 0;
  set_computers_number[next_set_id] = 1;
  set_type[next_set_id] = 1; // all items (single item in fact) have computers
  next_set_id++;
}

void new_set_double(int x, int y) {
  // printf("! new_set_double %d %d\n", x, y);
  parent[x] = -1;
  parent[y] = x;
  node_to_set_id[x] = next_set_id;
  set_rank[next_set_id] = 1;
  set_computers_number[next_set_id] = 1;
  set_type[next_set_id] = -1; // all items may have computers, but not sure
  next_set_id++;
}

void join_item_to_set(int x_parent, int y_new) {
  // printf("! join_item_to_set %d %d\n", x_parent, y_new);
  int set_id;

  parent[y_new] = x_parent;
  set_id = node_to_set_id[x_parent];
  if (set_rank[set_id] == 0) {
    set_rank[set_id]++;
  }
  set_computers_number[set_id]++;
  if (set_computers_number[set_id] == 1) { // we jumped back from 0 to 1, so we need to change type from sure not-owner to maybe owner
    set_type[set_id] = -1;
  }
}

void convert_set_to_sure_owners(int set_id) {
  // printf("! convert_set_to_sure_owners %d\n", set_id);
  set_computers_number[set_id]++;
  set_type[set_id] = 1;
}

void join_sets(int x_parent, int y_parent) {
  // printf("! join_sets %d %d\n", x_parent, y_parent);
  int x_set_id = node_to_set_id[x_parent];
  int y_set_id = node_to_set_id[y_parent];
  if (set_rank[x_set_id] > set_rank[y_set_id]) { // set x absorbs "smaller" y
    parent[y_parent] = x_parent;
    set_computers_number[x_set_id] += set_computers_number[y_set_id] + 1;
    if (set_type[y_set_id] == 1) { // if absorbed set was "sure owners", then new combined set also is
      set_type[x_set_id] = 1;
    } else if (set_type[x_set_id] == 0) { // we can land with type 0 (sure not-owners) after break_computer calls
      set_type[x_set_id] = -1;
    }
  } else if (set_rank[x_set_id] < set_rank[y_set_id]) { // set y absorbs "smaller" x
    parent[x_parent] = y_parent;
    set_computers_number[y_set_id] += set_computers_number[x_set_id] + 1;
    if (set_type[x_set_id] == 1) { // if absorbed set was "sure owners", then new combined set also is
      set_type[y_set_id] = 1;
    } else if (set_type[y_set_id] == 0) { // we can land with type 0 (sure not-owners) after break_computer calls
      set_type[y_set_id] = -1;
    }
  } else { // the same rank, but set x absorbs "smaller" y (and we update rank)
    parent[y_parent] = x_parent;
    set_computers_number[x_set_id] += set_computers_number[y_set_id] + 1;
    if (set_type[y_set_id] == 1) { // if absorbed set was "sure owners", then new combined set also is
      set_type[x_set_id] = 1;
    } else if (set_type[x_set_id] == 0) { // we can land with type 0 (sure not-owners) after break_computer calls
      set_type[x_set_id] = -1;
    }
    set_rank[x_set_id]++;
  }
}

int find_parent(int x) {
  // printf("! find_parent %d\n", x);
  if (parent[x] == 0) {
    return 0;
  } else if (parent[x] == -1) {
    return x;
  } else {
    parent[x] = find_parent(parent[x]);
    return parent[x];
  }
}

void break_computer(int x) {
  // printf("! break_computer %d\n", x);
  int parent_x = find_parent(x);
  int set_id = node_to_set_id[parent_x];
  set_computers_number[set_id]--;
  if (set_computers_number[set_id] == 0) { // if that was the last computer, then the rest in the group are "sure not-owners" (should be 0 or 1 items left)
    set_type[set_id] = 0;
  }

  // generate new id for the broken computer node
  real_id[reverse_real_id[x]] = next_real_id;
  reverse_real_id[next_real_id] = reverse_real_id[x];
  parent[next_real_id] = 0;
  next_real_id++;
}

int main() {
  scanf("%d %d", &n, &q);

  next_set_id = 1;
  next_real_id = n + 1;

  for (i = 1; i <= n; i++) {
    parent[i] = 0;
    // node_to_set_id[i] = 0; // TODO: probably not needed (double check)
    real_id[i] = i;
    reverse_real_id[i] = i;
  }

  i = 0;

  while (i < q) {
    scanf("%c", &operation);

    if (operation == '+') {
      i++;
      scanf("%d %d", &a, &b);
      if (a == b) {
        a = real_id[a];
        int parent_a = find_parent(a);
        if (parent_a == 0) { // node doesn't belong to any group yet
          new_set_single(a);
        } else { // node belongs to group => this group needs to be of type -1 => convert type to 1
          convert_set_to_sure_owners(node_to_set_id[parent_a]);
        }
      } else {
        a = real_id[a];
        b = real_id[b];

        int parent_a = find_parent(a);
        int parent_b = find_parent(b);

        // printf("! received + %d %d %d %d\n", a, b, parent_a, parent_b);

        if ((parent_a == 0) && (parent_b == 0)) { // both nodes don't belong to any group yet
          new_set_double(a, b);
        } else if (parent_b == 0) { // node b doesn't belong to any group yet
          join_item_to_set(parent_a, b);
        } else if (parent_a == 0) { // node a doesn't belong to any group yet
          join_item_to_set(parent_b, a);
        } else if (parent_a == parent_b) { // both nodes are from the same set => all in set becomes sure owners
          convert_set_to_sure_owners(node_to_set_id[parent_a]);
        } else { // nodes from different sets, we need to join those sets together
          join_sets(parent_a, parent_b);
        }
      }
    } else if (operation == '-') {
      i++;
      scanf("%d", &a);
      a = real_id[a];
      break_computer(a);
    } else if (operation == '?') { // without this condition we go here with read \n \r or other white space
      i++;
      scanf("%d", &a);
      a = real_id[a];
      int parent_a = find_parent(a);
      if (parent_a == 0) {
        // printf("=> 0\n");
        printf("0");
      } else {
        int set_id = node_to_set_id[parent_a];
        if (set_type[set_id] == 0) {
          // printf("=> 0\n");
          printf("0");
        } else if (set_type[set_id] == 1) {
          // printf("=> 1\n");
          printf("1");
        } else { // set_type[set_id] == -1
          // printf("=> ?\n");
          printf("?");
        }
      }
    }
  }

  printf("\n");

  return 0;
}