#include<bits/stdc++.h> using namespace std; const int N = 1500005; int label[N]; int lider[N]; int mode[N]; int sz[N]; int act_label; int f(int a) { if(lider[a] != a) lider[a] = f(lider[a]); return lider[a]; } void u(int a, int b) { int c = f(a), d = f(b); if(c == d) mode[c] = 1; else { lider[c] = d; sz[d] += sz[c]; if(mode[c] == 1 || mode[d] == 1) mode[d] = 1; else mode[d] = 0; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int a, t; cin>>a>>t; for(int x = 1; x <= a; x++) { label[x] = x; lider[x] = x; sz[x] = 1; } act_label = a + 1; while(t--) { char b; cin>>b; if(b == '?') { int c; cin>>c; int pom = f(label[c]); if(mode[pom] == 1) cout<<1; else if(sz[pom] == 1) cout<<0; else cout<<'?'; } else if(b == '+') { int c, d; cin>>c>>d; u(label[c] ,label[d]); } else if(b == '-') { int c; cin>>c; sz[f(label[c])]--; label[c] = act_label; lider[act_label] = act_label; sz[act_label++] = 1; } } 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 | #include<bits/stdc++.h> using namespace std; const int N = 1500005; int label[N]; int lider[N]; int mode[N]; int sz[N]; int act_label; int f(int a) { if(lider[a] != a) lider[a] = f(lider[a]); return lider[a]; } void u(int a, int b) { int c = f(a), d = f(b); if(c == d) mode[c] = 1; else { lider[c] = d; sz[d] += sz[c]; if(mode[c] == 1 || mode[d] == 1) mode[d] = 1; else mode[d] = 0; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int a, t; cin>>a>>t; for(int x = 1; x <= a; x++) { label[x] = x; lider[x] = x; sz[x] = 1; } act_label = a + 1; while(t--) { char b; cin>>b; if(b == '?') { int c; cin>>c; int pom = f(label[c]); if(mode[pom] == 1) cout<<1; else if(sz[pom] == 1) cout<<0; else cout<<'?'; } else if(b == '+') { int c, d; cin>>c>>d; u(label[c] ,label[d]); } else if(b == '-') { int c; cin>>c; sz[f(label[c])]--; label[c] = act_label; lider[act_label] = act_label; sz[act_label++] = 1; } } return 0; } |