#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"); }
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"); } |