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
101
102
#include <cstdio>
#include <algorithm>

#define MAX 300100
#define MAX2 1000100


struct Grupa {
    int komp;
    int ludzi;
    Grupa * moja;
};

int n,q,a,b,c,d;
Grupa * g[MAX];
Grupa ng[MAX2];
int ng_ile=1;
char ch;

Grupa *get_p(Grupa * &a) {
    if(a == nullptr) return nullptr;
    if(a->moja == a) return a;
    Grupa * result = get_p(a->moja);
    a = result;
    return result;
}

Grupa *get(int a) {
    return get_p(g[a]);    
}

Grupa *get_n(int a) {
    Grupa * ga = get(a);
    if (ga == nullptr) {
        ga = &ng[ng_ile++];
        ga->ludzi = 1;
        ga->komp = 0;
        g[a] = ga->moja = ga;
    }
    return ga;
}

void dodaj(int a, int b) {
    Grupa *ga = get_n(a);
    Grupa *gb = get_n(b);
    if (ga == gb) {
        ga->komp += 1;
    } else {
        if (ga->ludzi < gb->ludzi) std::swap(ga,gb);
        ga->ludzi += gb->ludzi;
        ga->komp += gb->komp + 1;
        gb->moja = ga;
    }
}
    
void usun(int a) {
    Grupa *ga = get(a);
    ga->ludzi--;
    ga->komp--;
    g[a] = nullptr;
}

void zapytaj(int a) {
    Grupa *ga = get(a);
    if (ga == nullptr || ga->komp == 0) {
        printf("0");
    } else if (ga->ludzi == ga->komp) {
        printf("1");
    } else {
        printf("?");
    }
}

void print() {
    for(int i=1;i<=n;i++) {
        Grupa * ga = get(i);
        if (ga == nullptr) printf("%d: nullptr\n",i);
        else printf("%d: %p l:%d k:%d\n", i, ga, ga->ludzi, ga->komp);
    }
}

#define D(x)

int main () {
    scanf("%d %d",&n, &q);
    for(int i=0;i<q;i++) {
        scanf(" %c ", &ch);
        if (ch == '+') {
            scanf("%d %d", &a, &b);
            dodaj(a,b);
        } else if (ch == '-') {
            scanf("%d", &c);
            usun(c);
        } else {
            scanf("%d", &d);
            zapytaj(d);
        }
        D(print();
        printf("#############################\n");)
    }
    printf("\n");
}