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
/* 2024
 * Maciej Szeptuch
 */
#include <algorithm>
#include <cstdio>

const int MAX_CITIZENS = 300001;
const int MAX_GROUPS = MAX_CITIZENS + 1000001;

char query[2];
int computers[MAX_GROUPS];
int group[MAX_GROUPS];
int groups;
int queries;
int size[MAX_GROUPS];

void join(int a, int b);
void remove(int a);
int find(int a);

int main(void)
{
    scanf("%d %d", &groups, &queries);
    for(int g = 0; g < groups; ++g)
    {
        group[g] = MAX_CITIZENS + g;
        group[group[g]] = group[g];
        size[group[g]] = 1;
    }

    for(int q = 0; q < queries; ++q)
    {
        int a = 0;
        int b = 0;
        scanf("%s %d", query, &a);
        --a;
        switch(query[0])
        {
        case '+':
            scanf("%d", &b);
            --b;
            join(a, b);
            break;

        case '-':
            remove(a);
            break;

        case '?':
            b = find(a);
            if(size[b] == 1)
                putchar(computers[b] ? '1' : '0');
            else if(size[b] == computers[b])
                putchar('1');
            else
                putchar('?');
            break;
        }
    }

    puts("");
    return 0;
}

void join(int a, int b)
{
    a = find(a);
    b = find(b);
    if(a == b)
    {
        ++computers[a];
        return;
    }

    if(size[a] > size[b])
        std::swap(a, b);

    size[b] += size[a];
    computers[b] += computers[a] + 1;
    group[a] = b;
}

inline void remove(int a)
{
    int _a = find(a);
    --size[_a];
    --computers[_a];

    group[a] = MAX_CITIZENS + groups++;
    group[group[a]] = group[a];
    size[group[a]] = 1;
}

inline int find(int a)
{
    if(group[a] == a)
        return a;

    return group[a] = find(group[a]);
}