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
#include <bits/stdc++.h>
using namespace std;
const int maxN=3e5+10;
int n, q, in1, in2;
char type;
int grupa[maxN];
int rep[maxN*8], akt_grupa=1, sizee[maxN*8];
bool czy_one[maxN*8];

int Find(int x)
{
    x=grupa[x];
    if(x!=rep[x])
        rep[x]=Find(x);
    return rep[x];
}
void Union(int x, int y)
{
    int x_pom=Find(x);
    int y_pom=Find(y);
    if(x_pom==0)
    {
        grupa[x]=akt_grupa;
        x_pom=akt_grupa;
        sizee[akt_grupa]=1;
        rep[akt_grupa]=akt_grupa;
        akt_grupa++;
        y_pom=Find(y);
    }
    if(y_pom==0)
    {
        grupa[y]=akt_grupa;
        y_pom=akt_grupa;
        sizee[akt_grupa]=1;
        rep[akt_grupa]=akt_grupa;
        akt_grupa++;
    }
    if(y_pom==x_pom)
    {
        czy_one[x_pom]=1;
        return;
    } 
    if(sizee[x_pom]<sizee[y_pom]){ swap(x_pom, y_pom); swap(x, y);}
    sizee[x_pom]+=sizee[y_pom];
    grupa[y]=grupa[x];
    rep[y_pom]=rep[x_pom];
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    while(q--)
    {
        cin>>type;
        if(type=='+')
        {
            cin>>in1>>in2;
            Union(in1, in2);
        }
        if(type=='-')
        {
            cin>>in1;
            grupa[in1]=0;
        }
        if(type=='?')
        {
            cin>>in1;
            if(Find(in1)==0) cout<<0;
            else if(czy_one[Find(in1)]) cout<<1;
            else cout<<"?";
        }
    }

}