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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <algorithm>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>

struct Klaster {
	int l_mieszk;
	int l_kompow;
//	int cel; -- osobny wektor zeby szybciej szukac.
};

struct Stan {
	std::vector< int > mieszkancy;
	std::vector< Klaster > klastry;
	std::vector< int > cele;

	Stan(size_t sz) : mieszkancy(sz, -1)
	{
	}
};

int daj_klaster(int A, Stan& s) {
	if (s.mieszkancy[A] == -1) {
		int poz = s.klastry.size();
		s.klastry.emplace_back( Klaster{ 1, 0 } );
		s.cele.emplace_back(poz);
		s.mieszkancy[A] = poz;
	}

	return s.mieszkancy[A];
}

int idz_do_lidera(int A, Stan& s) {
	std::vector< int > path;

	while (s.cele[A] != A) {
		path.push_back(A);
		A = s.cele[A];
	}

	for (auto el : path) {
		s.cele[el] = A;
	}

	return A;
}

void wstaw(int A, int B, Stan& s) {
	int kA = daj_klaster(A, s);
	int kB = daj_klaster(B, s);

	int lider_kA = idz_do_lidera(kA, s);
	int lider_kB = idz_do_lidera(kB, s);

	int lepszy = (s.klastry[lider_kA].l_mieszk < s.klastry[lider_kB].l_mieszk) ? lider_kB : lider_kA;
	int gorszy = (s.klastry[lider_kA].l_mieszk < s.klastry[lider_kB].l_mieszk) ? lider_kA : lider_kB;

	s.klastry[lepszy].l_kompow += 1;

	if (lepszy != gorszy) {
		s.klastry[lepszy].l_mieszk += s.klastry[gorszy].l_mieszk;
		s.klastry[lepszy].l_kompow += s.klastry[gorszy].l_kompow;
		s.cele[gorszy] = lepszy;
	}
}

void wywal(int A, Stan& s) {
	int kA = idz_do_lidera(s.mieszkancy[A], s);
	s.klastry[kA].l_mieszk -= 1;
	s.klastry[kA].l_kompow -= 1;

	s.mieszkancy[A] = -1;
}

char pytaj(int A, Stan& s) {

	if (s.mieszkancy[A] == -1) {
		return '0';
	}

	int kA = idz_do_lidera(s.mieszkancy[A], s);
	Klaster const& k = s.klastry[kA];

	if (k.l_kompow == 0) {
		return '0';
	}
	else if (k.l_mieszk == k.l_kompow) {
		return '1';
	}
	else {
		return '?';
	}
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);

	size_t l_mieszk;  std::cin >> l_mieszk;
	size_t l_zdarzen; std::cin >> l_zdarzen;

	Stan s(l_mieszk);

	for (size_t i = 0; i < l_zdarzen; ++i) {
		char typ_zd; std::cin >> typ_zd;

		if (typ_zd == '+') {
			int A; int B; std::cin >> A >> B; A--; B--;	
			wstaw(A, B, s);
		}
		else if (typ_zd == '-') {
			int A; std::cin >> A; A--;
			wywal(A, s); 
		}
		else if (typ_zd == '?') {
			int A; std::cin >> A; A--;
			std::cout << pytaj(A, s);
		}
	}
	std::cout << "\n";
}