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
119
120
121
122
123
124
125
126
127
128
129
130
#include<bits/stdc++.h>
using namespace std;
const int N = 300005;
int n;
struct node{
    bool isempty;
    bool smieciarka;
    int vert;
    int par;
    int siz;
    bool komputer;
};
struct fu{
    int self[N];
    vector<node> wierz;
    void init(){
        node nowanoda;
        for(int i=1; i<=n; i++){
            nowanoda.isempty = 0;
            nowanoda.smieciarka = 0;
            nowanoda.vert = i;
            nowanoda.par = i-1;
            nowanoda.siz = 1;
            nowanoda.komputer = 0;
            wierz.push_back(nowanoda);
            self[i] = i-1;
        }
    }
    int subfajnd(int v){ /// dajemy jej numerek do noda, on znajduje numerek do noda ktory jest rodzicem
        if(wierz[v].par == v) return v;
        int wynik = subfajnd(wierz[v].par);
        wierz[v].par = wynik;
        return wynik;
    }
    int fajnd(int v){ /// Dostaje numer domu, zwraca numer noda spojnej w ktorej ten dom ma byc, gwarancja ze to nie smieciarka
        int wstep = subfajnd(self[v]);
        node znaleziona = wierz[wstep];
        if(znaleziona.smieciarka){
            wierz[self[v]].isempty = 1;
            self[v] = wierz.size();
            node nowanoda;
            nowanoda.isempty = 0;
            nowanoda.smieciarka = 0;
            nowanoda.vert = v;
            nowanoda.par = self[v];
            nowanoda.siz = 1;
            nowanoda.komputer = 1;
            wierz.push_back(nowanoda);
            return self[v];
        }
        return wstep;
    }
    void junion(int a, int b){ /// Dostaje numery domow, robi union spojnych zawierajacych nody tych domow
        int anum = fajnd(a);
        int bnum = fajnd(b);
        node anode = wierz[anum];
        node bnode = wierz[bnum];
        if(anode.siz==1&&anode.komputer){
            wierz[anum].smieciarka = 1;
            wierz[bnum].smieciarka = 1;
        }
        if(bnode.siz==1&&bnode.komputer){
            wierz[anum].smieciarka = 1;
            wierz[bnum].smieciarka = 1;
        }
        if(anode.siz>bnode.siz){
            wierz[anum].siz+=bnode.siz;
            wierz[bnum].par = anum;
        }
        else{
            wierz[bnum].siz+=anode.siz;
            wierz[anum].par = bnum;
        }
    }
    void dilit(int v){ ///Dostaje numerek domu, zastepuje jego nodę pustą nodą i tworzy własną nowa node dla tego domu
        wierz[self[v]].isempty = 1;
        int parentNode = fajnd(v);
        wierz[parentNode].siz--;
        self[v] = wierz.size();
        node nowanoda;
        nowanoda.isempty = 0;
        nowanoda.smieciarka = 0;
        nowanoda.vert = v;
        nowanoda.par = self[v];
        nowanoda.siz = 1;
        nowanoda.komputer = 0;
        wierz.push_back(nowanoda);
    }
    char kuery(int v){
        int parentNode = fajnd(v);
        if(wierz[parentNode].siz>1) return('?');
        if(wierz[self[v]].komputer) return ('1');
        return('0');
    }
    void add(int a, int b){
        int apar = fajnd(a);
        int bpar = fajnd(b);
        ///cout << apar<<" vs "<<bpar<<" ";
        if(apar==bpar){
            ///cout << "smiec"<<a<<" "<< b<<" ";
            wierz[apar].smieciarka=1;
            return;
        }
        junion(a, b);
    }
};
fu solv;
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int q, a, b;
    char znak;
    cin >> n >> q;
    solv.init();
    for(int i=0; i<q; i++){
        cin >> znak;
        if(znak == '+'){
            cin >> a >> b;
            solv.add(a, b);
        }
        if(znak== '-'){
            cin >> a;
            solv.dilit(a);
        }
        if(znak == '?'){
            cin >> a;
            cout << solv.kuery(a);
        }
    }
}