#include<bits/stdc++.h> using namespace std; #define pb push_back #define pii pair<int, int> #define st first #define nd second #define sz(x) (int)(x).size() #define all(x) (x).begin(), (x).end() const int MAXN = 300'009; int type[MAXN]; int p[MAXN]; vector<int> V[MAXN]; int pos[MAXN]; vector<int> available; int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, q; cin >> n >> q; for(int i=1;i<=n;i++) { p[i] = i; V[i] = {i}; } while(q--) { char c; cin >> c; if(c=='?') { int x; cin >> x; if(type[x]==2) cout << "?"; else cout << type[x]; } if(c=='+') { int a, b; cin >> a >> b; int A = p[a], B = p[b]; if(A==B) { if(type[V[A][0]]!=1) { for(int x:V[A]) { type[x] = 1; } } } else { int val = 2; if(type[V[A][0]]==1||type[V[B][0]]==1) val = 1; if(type[V[A][0]]!=val) { for(int x:V[A]) type[x] = val; } if(type[V[B][0]]!=val) { for(int x:V[B]) type[x] = val; } if(sz(V[A])<sz(V[B])) { swap(A, B); } for(int x:V[B]) { pos[x] = sz(V[A]); V[A].pb(x); p[x] = A; } V[B].clear(); available.pb(B); } } if(c=='-') { int a; cin >> a; int A = p[a]; pos[V[A].back()] = pos[a]; swap(V[A][pos[a]], V[A].back()); V[A].pop_back(); if(sz(V[A])==0) available.pb(A); int num = available.back(); available.pop_back(); pos[a] = 0; V[num] = {a}; p[a] = num; type[a] = 0; if(sz(V[A])==1&&type[V[A][0]]==2) { type[V[A][0]] = 0; } } } cout << "\n"; }
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 | #include<bits/stdc++.h> using namespace std; #define pb push_back #define pii pair<int, int> #define st first #define nd second #define sz(x) (int)(x).size() #define all(x) (x).begin(), (x).end() const int MAXN = 300'009; int type[MAXN]; int p[MAXN]; vector<int> V[MAXN]; int pos[MAXN]; vector<int> available; int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, q; cin >> n >> q; for(int i=1;i<=n;i++) { p[i] = i; V[i] = {i}; } while(q--) { char c; cin >> c; if(c=='?') { int x; cin >> x; if(type[x]==2) cout << "?"; else cout << type[x]; } if(c=='+') { int a, b; cin >> a >> b; int A = p[a], B = p[b]; if(A==B) { if(type[V[A][0]]!=1) { for(int x:V[A]) { type[x] = 1; } } } else { int val = 2; if(type[V[A][0]]==1||type[V[B][0]]==1) val = 1; if(type[V[A][0]]!=val) { for(int x:V[A]) type[x] = val; } if(type[V[B][0]]!=val) { for(int x:V[B]) type[x] = val; } if(sz(V[A])<sz(V[B])) { swap(A, B); } for(int x:V[B]) { pos[x] = sz(V[A]); V[A].pb(x); p[x] = A; } V[B].clear(); available.pb(B); } } if(c=='-') { int a; cin >> a; int A = p[a]; pos[V[A].back()] = pos[a]; swap(V[A][pos[a]], V[A].back()); V[A].pop_back(); if(sz(V[A])==0) available.pb(A); int num = available.back(); available.pop_back(); pos[a] = 0; V[num] = {a}; p[a] = num; type[a] = 0; if(sz(V[A])==1&&type[V[A][0]]==2) { type[V[A][0]] = 0; } } } cout << "\n"; } |