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
#include <bits/stdc++.h>

using namespace std;

struct wierzcholek{
    int ojciec;
    int typ = 0;
    int wielkosc = 1;
};

int korzen(int w, vector<wierzcholek>&v);

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,q;
    char znak;
    cin >> n >> q;
    vector<int>pozycje(n+1);
    for(int i=1; i<=n;i++){
        pozycje[i]=i;
    }
    vector<wierzcholek>v(n+1);
    for(int i=1; i<=n; i++){
        v[i].ojciec = i;
    }
    int k1,k2,a,b;
    wierzcholek nowy;
    string wynik="";
    for(int j=0; j<q; j++){
        cin >> znak >> a;
        k1 = korzen(pozycje[a],v);
        if(znak=='+'){
            cin >> b;
            k2 = korzen(pozycje[b],v);
            if(k1==k2){
                v[k1].typ++;
                if(v[k1].typ==1)v[k1].typ++;
            }else{
                if(v[k1].typ > v[k2].typ){
                    v[k2].ojciec=k1;
                    v[k1].wielkosc+=v[k2].wielkosc;
                }else{
                    v[k1].ojciec=k2;
                    v[k2].wielkosc+=v[k1].wielkosc;
                }
                if(v[k1].typ==0 && v[k2].typ==0){
                    v[k1].typ++;
                    v[k2].typ++;
                }
            }
        }
        if(znak=='-'){
            v[k1].wielkosc--;
            if(v[k1].wielkosc==1 && v[k1].typ==1){
                v[k1].typ = 0;
            }
            v.push_back(nowy);
            pozycje[a] = v.size()-1;
            v[v.size()-1].ojciec = v.size()-1;
        }
        if(znak=='?'){
            if(v[k1].typ == 0){
                wynik+='0';
            }
            if(v[k1].typ == 1){
                wynik+='?';
            }
            if(v[k1].typ == 2){
                wynik+='1';
            }
        }
    }
    cout << wynik << endl;
    return 0;
}

int korzen(int w, vector<wierzcholek>&v){
    if(v[w].ojciec == w){
        return w;
    }
    int a = korzen(v[w].ojciec, v);
    v[w].ojciec = a;
    return a;
}