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
// basicly the same but with breaking computers
#include <bits/stdc++.h>

using namespace std;

void give(vector<int>& idx, vector<int>& state, vector<unordered_set<int>>& components, int p) {
    while(components[p].size()) {
        idx[*components[p].begin()] = -1;
        state[*components[p].begin()] = 2;
        components[p].erase(components[p].begin());
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, q;
    cin >> n >> q;
    vector<int> state(n, 1);
    vector<int> idx(n);
    vector<unordered_set<int>> components(n);
    for(int i = 0; i < n; i++) {
        idx[i] = i;
        components[i].insert(i);
    }

    for(int i = 0; i < q; i++) {
        char query;
        cin >> query;
        if(query == '?') {
            int d;
            cin >> d;
            d--;
            if(state[d] == 0) cout << '?';
            else if(state[d] == 1) cout << '0';
            else cout << '1';
        } else if (query == '+') {
            int a, b;
            cin >> a >> b;
            a--; b--;
            int p = idx[a], q = idx[b];

            //also need to check if state[a] or state[b] equals 2
            if(state[a] == 2 || state[b] == 2) {
                if(state[a] < state[b]) {
                    give(idx, state, components, p);
                } else {
                    give(idx, state, components, q);
                }
            }
            else if(p != q) {
                if(components[p].size() == 1) state[a] = 0;
                if(components[q].size() == 1) state[b] = 0;

                if(components[p].size() < components[q].size()) swap(p, q);

                while(components[q].size()) {
                    idx[*components[q].begin()] = p;
                    components[p].insert(*components[q].begin());
                    components[q].erase(components[q].begin());
                }
            } else {
                give(idx, state, components, p);
            }
        } else {
            int c;
            cin >> c;
            c--;
            int p = idx[c];
            state[c] = 1;
            idx[c] = components.size();
            components.push_back({c});
            if(p != -1) {
                components[p].erase(c);
                if(components[p].size() == 1) {
                    state[*components[p].begin()] = 1;
                }
            }
        }
    }
}