#include<bits/stdc++.h> using namespace std; const int N=2e6+7; int n,q,yu; int fa[N],sz[N],ok[N],chk[N],nw[N]; int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);} signed main(){ ios::sync_with_stdio(0); cin.tie(0);cin>>n>>q;yu=n; for(int i=1;i<N;i++){ fa[i]=i; sz[i]=1; } for(int i=1;i<=n;i++) nw[i]=i; for(int i=1;i<=q;i++){ char c; int x,y; cin>>c; if(c=='?'){ cin>>x; int u=find(nw[x]); if(chk[u]==sz[u]){ cout<<"1"; }else if((chk[u]==sz[u]-1&&ok[u]==chk[u])||chk[u]==0){ cout<<"0"; }else cout<<"?"; }else if(c=='-'){ cin>>x; ok[find(nw[x])]++; nw[x]=++yu; }else{ cin>>x>>y; x=nw[x];y=nw[y]; if(find(x)==find(y))chk[find(x)]++; else{ int fx=find(x),fy=find(y); fa[fx]=fy; sz[fy]+=sz[fx]; chk[fy]+=chk[fx]+1; ok[fy]+=ok[fx]; } } }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 | #include<bits/stdc++.h> using namespace std; const int N=2e6+7; int n,q,yu; int fa[N],sz[N],ok[N],chk[N],nw[N]; int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);} signed main(){ ios::sync_with_stdio(0); cin.tie(0);cin>>n>>q;yu=n; for(int i=1;i<N;i++){ fa[i]=i; sz[i]=1; } for(int i=1;i<=n;i++) nw[i]=i; for(int i=1;i<=q;i++){ char c; int x,y; cin>>c; if(c=='?'){ cin>>x; int u=find(nw[x]); if(chk[u]==sz[u]){ cout<<"1"; }else if((chk[u]==sz[u]-1&&ok[u]==chk[u])||chk[u]==0){ cout<<"0"; }else cout<<"?"; }else if(c=='-'){ cin>>x; ok[find(nw[x])]++; nw[x]=++yu; }else{ cin>>x>>y; x=nw[x];y=nw[y]; if(find(x)==find(y))chk[find(x)]++; else{ int fx=find(x),fy=find(y); fa[fx]=fy; sz[fy]+=sz[fx]; chk[fy]+=chk[fx]+1; ok[fy]+=ok[fx]; } } }cout<<"\n"; return 0; } |