#include <iostream> #include <vector> using namespace std; class UnionFind { private: struct Node { int parent; int size; short rank; bool full; }; vector<Node> V; int find(int x) { if (V[x].parent == x) return x; return V[x].parent = find(V[x].parent); } public: UnionFind(int init_size) : V(init_size) { for (int i=0; i<init_size; i++) V[i] = {i, 1, 0, false}; } void merge(int x, int y) { x = find(x); y = find(y); if (x==y) { V[x].full = true; return; } if (V[y].rank > V[x].rank) swap(x, y); else if (V[y].rank == V[x].rank) V[x].rank++; if (V[y].full) V[x].full = true; V[y].parent = x; V[x].size += V[y].size; } int new_node() { int id = V.size(); V.push_back({id, 1, 0, false}); return id; } void delete_node(int x) { V[find(x)].size--; } bool is_full(int x) { return V[find(x)].full; } bool is_single(int x) { return V[find(x)].size == 1; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; UnionFind uf(n); vector<int>R(n+1); for (int i=1; i<=n; i++) R[i] = i-1; while (q--) { string op; int x, y; cin >> op >> x; if (op == "+") { cin >> y; uf.merge(R[x], R[y]); } else if (op == "-") { uf.delete_node(R[x]); R[x] = uf.new_node(); } else { if (uf.is_full(R[x])) cout << '1'; else if (uf.is_single(R[x])) cout << '0'; else cout << '?'; } } cout << '\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 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 | #include <iostream> #include <vector> using namespace std; class UnionFind { private: struct Node { int parent; int size; short rank; bool full; }; vector<Node> V; int find(int x) { if (V[x].parent == x) return x; return V[x].parent = find(V[x].parent); } public: UnionFind(int init_size) : V(init_size) { for (int i=0; i<init_size; i++) V[i] = {i, 1, 0, false}; } void merge(int x, int y) { x = find(x); y = find(y); if (x==y) { V[x].full = true; return; } if (V[y].rank > V[x].rank) swap(x, y); else if (V[y].rank == V[x].rank) V[x].rank++; if (V[y].full) V[x].full = true; V[y].parent = x; V[x].size += V[y].size; } int new_node() { int id = V.size(); V.push_back({id, 1, 0, false}); return id; } void delete_node(int x) { V[find(x)].size--; } bool is_full(int x) { return V[find(x)].full; } bool is_single(int x) { return V[find(x)].size == 1; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; UnionFind uf(n); vector<int>R(n+1); for (int i=1; i<=n; i++) R[i] = i-1; while (q--) { string op; int x, y; cin >> op >> x; if (op == "+") { cin >> y; uf.merge(R[x], R[y]); } else if (op == "-") { uf.delete_node(R[x]); R[x] = uf.new_node(); } else { if (uf.is_full(R[x])) cout << '1'; else if (uf.is_single(R[x])) cout << '0'; else cout << '?'; } } cout << '\n'; return 0; } |