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
#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <set>
using namespace std;
vector <int> szef,lud,komp;   //---------
vector <set<int>>boss;
int find(int a)
{
    if(szef[a]==a) return a;
    int b=find(szef[a]);
    boss[szef[a]].erase(a);
    szef[a]=b;
    boss[szef[a]].insert(a);
    return szef[a];
}
void onion(int a,int b)
{
    int c=find(a),d=find(b);
    if(c==d)
    {
        komp[c]++;
        return;
    }
   if(rand()%2==1)
   {
       int x=c;
       c=d;
       d=x;
   }
   szef[d]=c;
   boss[c].insert(d);
   komp[c]+=komp[d]+1;
   lud[c]+=lud[d];
}
int main()
{
    srand(time(NULL));
    cin.tie(0)->sync_with_stdio(false);
    int n,q;
    cin>>n>>q;
    szef.resize(n);
    lud.resize(n);
    komp.resize(n);
    boss.resize(n);
    for(int i=0;i<n;i++)
    {
        szef[i]=i;
        lud[i]=1;
        komp[i]=0;
        boss[i].clear();
    }
    for(int i=0;i<q;i++)
    {
        int a,b;
        char bubus;
        cin>>bubus;
        if(bubus=='+')
        {
            cin>>a>>b;
            a--;
            b--;
            onion(a,b);
        }
        if(bubus=='?')
        {
            cin>>a;
            a--;
            b=find(a);
            if(komp[b]==0) cout<<0;
            else
            {
                if(komp[b]==lud[b]) cout<<1;
                else cout<<"?";
            }
        }
        if(bubus=='-')
        {
            cin>>a;
            a--;
            b=find(a);
            if(a==b&&boss[a].size()!=0)
            {
                b=*boss[a].begin();
                lud[b]=lud[a];
                komp[b]=komp[a];
                szef[b]=b;
            }
            set<int>:: iterator itr;
                for(itr=boss[a].begin();itr!=boss[a].end();itr++)
                    {
                        szef[*itr]=b;
                        if(*itr!=b) boss[b].insert(*itr);
                    }
            boss[b].erase(a);
            lud[b]--;
            komp[b]--;
            szef[a]=a;
            lud[a]=1;
            komp[a]=0;
            boss[a].clear();
        }
    }
}