#include <bits/stdc++.h>
#define scanf(...) scanf(__VA_ARGS__)?:0
using namespace std;
int n, q;
int skl[300005], poz[300005];
vector<int> s[300005];
int zajeta[300005];
vector<int> wolne;
int main() {
scanf("%d%d", &n, &q);
for (int i=1; i<=n; i++) {
skl[i] = i;
s[i].push_back(i);
}
wolne.push_back(n+1);
for (int i=0; i<q; i++) {
char z;
scanf(" %c", &z);
if (z == '+') {
int a, b;
scanf("%d%d", &a, &b);
if (skl[a] == skl[b]) zajeta[skl[a]] = 1;
else {
int s1 = skl[a], s2 = skl[b];
if (s[s1].size() < s[s2].size()) {
for (int i: s[s1]) {
skl[i] = s2;
poz[i] = s[s2].size();
s[s2].push_back(i);
}
s[s1].clear();
wolne.push_back(s1);
if (zajeta[s1]) zajeta[s2] = 1;
zajeta[s1] = 0;
} else {
for (int i: s[s2]) {
skl[i] = s1;
poz[i] = s[s1].size();
s[s1].push_back(i);
}
s[s2].clear();
wolne.push_back(s2);
if (zajeta[s2]) zajeta[s1] = 1;
zajeta[s2] = 0;
}
}
} else {
int c;
scanf("%d", &c);
if (z == '-') {
int s1 = skl[c];
if ((int) s[s1].size() > 1) {
int num = s[s1].back();
poz[num] = poz[c];
swap(s[s1][poz[c]], s[s1].back());
s[s1].pop_back();
skl[c] = wolne.back();
wolne.pop_back();
s[skl[c]].push_back(c);
poz[c] = 0;
zajeta[skl[c]] = 0;
} else {
zajeta[s1] = 0;
}
} else {
if (zajeta[skl[c]]) putchar('1');
else if ((int) s[skl[c]].size() == 1) putchar('0');
else putchar('?');
}
}
}
puts("");
}
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 | #include <bits/stdc++.h> #define scanf(...) scanf(__VA_ARGS__)?:0 using namespace std; int n, q; int skl[300005], poz[300005]; vector<int> s[300005]; int zajeta[300005]; vector<int> wolne; int main() { scanf("%d%d", &n, &q); for (int i=1; i<=n; i++) { skl[i] = i; s[i].push_back(i); } wolne.push_back(n+1); for (int i=0; i<q; i++) { char z; scanf(" %c", &z); if (z == '+') { int a, b; scanf("%d%d", &a, &b); if (skl[a] == skl[b]) zajeta[skl[a]] = 1; else { int s1 = skl[a], s2 = skl[b]; if (s[s1].size() < s[s2].size()) { for (int i: s[s1]) { skl[i] = s2; poz[i] = s[s2].size(); s[s2].push_back(i); } s[s1].clear(); wolne.push_back(s1); if (zajeta[s1]) zajeta[s2] = 1; zajeta[s1] = 0; } else { for (int i: s[s2]) { skl[i] = s1; poz[i] = s[s1].size(); s[s1].push_back(i); } s[s2].clear(); wolne.push_back(s2); if (zajeta[s2]) zajeta[s1] = 1; zajeta[s2] = 0; } } } else { int c; scanf("%d", &c); if (z == '-') { int s1 = skl[c]; if ((int) s[s1].size() > 1) { int num = s[s1].back(); poz[num] = poz[c]; swap(s[s1][poz[c]], s[s1].back()); s[s1].pop_back(); skl[c] = wolne.back(); wolne.pop_back(); s[skl[c]].push_back(c); poz[c] = 0; zajeta[skl[c]] = 0; } else { zajeta[s1] = 0; } } else { if (zajeta[skl[c]]) putchar('1'); else if ((int) s[skl[c]].size() == 1) putchar('0'); else putchar('?'); } } } puts(""); } |
English