#include <bits/stdc++.h> #define MAXN 310000 #define MAXNQ 1100000 + MAXN #define st first #define nd second using namespace std; int repr[MAXNQ]; int mapping[MAXN]; int spsize[MAXNQ]; bool surey[MAXNQ]; int findd(int x) { if(repr[x] == x) return x; return repr[x] = findd(repr[x]); } void unionn(int x, int y) { x = findd(x); y = findd(y); if(x==y) surey[x] = 1; else { repr[x] = y; spsize[y] += spsize[x]; surey[y] |= surey[x]; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, q; cin>>n>>q; int last=n+2; for(int i=0; i<MAXN; i++) mapping[i]=i; for(int i=0; i<MAXNQ; i++) { repr[i]=i; } for(int i=0; i<q; i++) { char t; int x,y; cin>>t; if(t=='+') { cin>>x>>y; x = mapping[x]; y = mapping[y]; unionn(x,y); spsize[findd(x)]++; } else if(t=='-') { cin>>x; spsize[findd(mapping[x])]--; mapping[x] = last++; } else { cin>>x; x = mapping[x]; x = findd(x); if(spsize[x] == 0) cout<<"0"; else if(surey[x]) cout<<"1"; else cout<<"?"; } // cout<<"\n??? "<<" "<<mapping[1]<<" "<<findd(mapping[1])<<" "<<mapping[3]<<" "<<findd(mapping[3])<<" "<<spsize[10]<<"\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 | #include <bits/stdc++.h> #define MAXN 310000 #define MAXNQ 1100000 + MAXN #define st first #define nd second using namespace std; int repr[MAXNQ]; int mapping[MAXN]; int spsize[MAXNQ]; bool surey[MAXNQ]; int findd(int x) { if(repr[x] == x) return x; return repr[x] = findd(repr[x]); } void unionn(int x, int y) { x = findd(x); y = findd(y); if(x==y) surey[x] = 1; else { repr[x] = y; spsize[y] += spsize[x]; surey[y] |= surey[x]; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, q; cin>>n>>q; int last=n+2; for(int i=0; i<MAXN; i++) mapping[i]=i; for(int i=0; i<MAXNQ; i++) { repr[i]=i; } for(int i=0; i<q; i++) { char t; int x,y; cin>>t; if(t=='+') { cin>>x>>y; x = mapping[x]; y = mapping[y]; unionn(x,y); spsize[findd(x)]++; } else if(t=='-') { cin>>x; spsize[findd(mapping[x])]--; mapping[x] = last++; } else { cin>>x; x = mapping[x]; x = findd(x); if(spsize[x] == 0) cout<<"0"; else if(surey[x]) cout<<"1"; else cout<<"?"; } // cout<<"\n??? "<<" "<<mapping[1]<<" "<<findd(mapping[1])<<" "<<mapping[3]<<" "<<findd(mapping[3])<<" "<<spsize[10]<<"\n"; } } |