#include <bits/stdc++.h> using namespace std; #ifdef DEBUG auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;} auto operator<<(auto &o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";} #define debug(X) cerr << "["#X"]: " << X << '\n'; #else #define cerr if(0)cout #define debug(X) ; #endif using ll = long long; #define all(v) (v).begin(), (v).end() #define ssize(x) int(x.size()) #define fi first #define se second #define mp make_pair #define eb emplace_back struct UF { vector<int> e, val; vector<vector<int>> child; UF(int n): e(n, -1), val(n, 0), child(n) {} int get(int a) {return e[a] < 0 ? a : get(e[a]);} void unionn(int a, int b) { val[a] = -1; val[b] = -1; a = get(a); b = get(b); if(a == b) { set(a, 1); return; } if(-e[a] > -e[b]) swap(a, b); e[b] += e[a]; e[a] = b; child[b].eb(a); return; } void set(int a, int x) { val[a] = x; for(auto u : child[a]) set(u, x); child[a].clear(); e[a] = -1; } int get_val(int v) {return val[v];} }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; UF uf(n); string ans = ""; for(int i = 0; i < q; ++i) { char c; cin >> c; if (c == '+') { int a, b; cin >> a >> b; a--; b--; uf.unionn(a, b); } if (c == '-') { int v; cin >> v; uf.set(v-1, 0); } if (c == '?') { int v; cin >> v; int x = uf.get_val(v-1); if(x == -1) ans.push_back('?'); else ans.push_back('0'+x); } } cout << ans << '\n'; return 0; }
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 | #include <bits/stdc++.h> using namespace std; #ifdef DEBUG auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;} auto operator<<(auto &o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";} #define debug(X) cerr << "["#X"]: " << X << '\n'; #else #define cerr if(0)cout #define debug(X) ; #endif using ll = long long; #define all(v) (v).begin(), (v).end() #define ssize(x) int(x.size()) #define fi first #define se second #define mp make_pair #define eb emplace_back struct UF { vector<int> e, val; vector<vector<int>> child; UF(int n): e(n, -1), val(n, 0), child(n) {} int get(int a) {return e[a] < 0 ? a : get(e[a]);} void unionn(int a, int b) { val[a] = -1; val[b] = -1; a = get(a); b = get(b); if(a == b) { set(a, 1); return; } if(-e[a] > -e[b]) swap(a, b); e[b] += e[a]; e[a] = b; child[b].eb(a); return; } void set(int a, int x) { val[a] = x; for(auto u : child[a]) set(u, x); child[a].clear(); e[a] = -1; } int get_val(int v) {return val[v];} }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; UF uf(n); string ans = ""; for(int i = 0; i < q; ++i) { char c; cin >> c; if (c == '+') { int a, b; cin >> a >> b; a--; b--; uf.unionn(a, b); } if (c == '-') { int v; cin >> v; uf.set(v-1, 0); } if (c == '?') { int v; cin >> v; int x = uf.get_val(v-1); if(x == -1) ans.push_back('?'); else ans.push_back('0'+x); } } cout << ans << '\n'; return 0; } |