#include<cstdio> #include<vector> #include<algorithm> #include<iostream> #include <unordered_set> #include <memory> #include <unistd.h> using namespace std; int main(){ int n,q,a,b; char t; scanf("%d%d", &n, &q); shared_ptr<unordered_set<int>> nie = make_shared<unordered_set<int>>(); shared_ptr<unordered_set<int>> tak = make_shared<unordered_set<int>>(); vector<shared_ptr<unordered_set<int>>> v(n+1, nie); for(int i=0; i < q; i++){ scanf("\n%c", &t); if(t=='+'){ scanf("%d%d", &a, &b); if(v[a] == nie){ if(v[b]==nie){ if(a==b){ v[a]=tak; } else{ v[a] =make_shared<unordered_set<int>>(); //{a,b}; v[b] = v[a]; v[a]->insert(a); v[b]->insert(b); } } else if(v[b] == tak) v[a] = tak; else{ v[a]=v[b]; v[a]->insert(a); } } else if(v[a] == tak){ if(v[b]==nie) v[b] = tak; else{ auto x = std::make_shared<unordered_set<int>>(*v[b]); for(int i:*x) v[i] = tak; } } else{ if(v[b] == nie){ v[b]=v[a]; v[b]->insert(b); } else if(v[b] ==tak){ auto x = std::make_shared<unordered_set<int>>(*v[a]); for(int i: *x){ v[i] = tak; } } else{ if (v[a]==v[b]){ auto x = std::make_shared<unordered_set<int>>(*v[a]); for(int i:*x){ v[i] = tak; } } else if(v[a]->size() > v[b]->size()){ v[a]->merge(*v[b]); for(auto i:*v[b]) v[i] = v[a]; } else{ v[b]->merge(*v[a]); for(auto i:*v[a]) v[i] = v[b]; } } } } else if(t=='-'){ scanf("%d", &a); if(v[a] != tak){ if(v[a]->size() == 2){ auto x = std::make_shared<unordered_set<int>>(*v[a]); for(auto i:*x) v[i] = nie; } else v[a]->erase(a); v[a] = nie; } else v[a] = nie; } else{ scanf("%d", &a); if(v[a] == nie) printf("0"); else if(v[a] == tak) printf("1"); else printf("?"); } } }
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 | #include<cstdio> #include<vector> #include<algorithm> #include<iostream> #include <unordered_set> #include <memory> #include <unistd.h> using namespace std; int main(){ int n,q,a,b; char t; scanf("%d%d", &n, &q); shared_ptr<unordered_set<int>> nie = make_shared<unordered_set<int>>(); shared_ptr<unordered_set<int>> tak = make_shared<unordered_set<int>>(); vector<shared_ptr<unordered_set<int>>> v(n+1, nie); for(int i=0; i < q; i++){ scanf("\n%c", &t); if(t=='+'){ scanf("%d%d", &a, &b); if(v[a] == nie){ if(v[b]==nie){ if(a==b){ v[a]=tak; } else{ v[a] =make_shared<unordered_set<int>>(); //{a,b}; v[b] = v[a]; v[a]->insert(a); v[b]->insert(b); } } else if(v[b] == tak) v[a] = tak; else{ v[a]=v[b]; v[a]->insert(a); } } else if(v[a] == tak){ if(v[b]==nie) v[b] = tak; else{ auto x = std::make_shared<unordered_set<int>>(*v[b]); for(int i:*x) v[i] = tak; } } else{ if(v[b] == nie){ v[b]=v[a]; v[b]->insert(b); } else if(v[b] ==tak){ auto x = std::make_shared<unordered_set<int>>(*v[a]); for(int i: *x){ v[i] = tak; } } else{ if (v[a]==v[b]){ auto x = std::make_shared<unordered_set<int>>(*v[a]); for(int i:*x){ v[i] = tak; } } else if(v[a]->size() > v[b]->size()){ v[a]->merge(*v[b]); for(auto i:*v[b]) v[i] = v[a]; } else{ v[b]->merge(*v[a]); for(auto i:*v[a]) v[i] = v[b]; } } } } else if(t=='-'){ scanf("%d", &a); if(v[a] != tak){ if(v[a]->size() == 2){ auto x = std::make_shared<unordered_set<int>>(*v[a]); for(auto i:*x) v[i] = nie; } else v[a]->erase(a); v[a] = nie; } else v[a] = nie; } else{ scanf("%d", &a); if(v[a] == nie) printf("0"); else if(v[a] == tak) printf("1"); else printf("?"); } } } |