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
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
int n,q,a,b;
//std::vector<std::set<int>>sa;
std::vector<char>st;
std::vector<int>element_to_set;
std::vector<std::set<int>>sets_elements;
int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(NULL);
    std::cin>>n>>q;
    st.resize(n+1,'0');
    //sa.resize(n+1);
    char op;
    sets_elements.resize(n+q+1);
    for(int i=0;i<=n;i++){
        element_to_set.emplace_back(i);
        sets_elements[i].insert(i);
    }
    int last_set=n;
    for(int i=0;i<q;i++){
        std::cin>>op>>a;

        if(op == '+')
            std::cin>>b;
        if(op=='-'){
            if(st[a]=='?'){
                sets_elements[element_to_set[a]].erase(a);
                int set=element_to_set[a];
                last_set++;
                element_to_set[a]=last_set;
                sets_elements[last_set].insert(a);
                if(sets_elements[set].size()==1)
                    st[*sets_elements[set].begin()]='0';
            }
            st[a]='0';
        }
        //std::cerr<<op<<a<<b<<std::endl;
        if(op=='?')
            std::cout<<st[a];


        if(op=='+'){
            if(st[a]=='1')
                std::swap(a,b);

            if(st[b]=='1'||element_to_set[a]==element_to_set[b]){
                int set=element_to_set[a];
                //std::cerr<<"before loop"<<set<<std::endl;
                for(auto x:sets_elements[set]){
                    //std::cerr<<set<<"xxx: "<<x<<" "<<sets_elements.size()<<std::endl;
                    st[x]='1';
                    last_set++;
                    element_to_set[x]=last_set;
                    sets_elements[last_set].insert(x);
                }
                sets_elements[set].clear();
            }
            else{
                if(sets_elements[element_to_set[a]].size()>sets_elements[element_to_set[b]].size())
                    std::swap(a,b);
                int set=element_to_set[a];
                for(auto x:sets_elements[set]){
                    sets_elements[element_to_set[b]].insert(x);
                    element_to_set[x]=element_to_set[b];
                    //std::cerr<<"redirect"<<x<<" "<<b<<std::endl;
                    //for(auto y:sets_elements[element_to_set[b]])
                        //std::cerr<<y<<std::endl;
                }
                sets_elements[set].clear();
                st[a]='?';
                st[b]='?';
            }
            
        }
        //std::cerr<<"st "<<st[1]<<" "<<st[2]<<" "<<st[3]<<std::endl;
    }
    std::cout<<"\n";
}