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
#include <cstdio>
#include <vector>
#include <set>

using namespace std;

int main () {
	int n, q;
	scanf("%d %d\n", &n, &q);
	vector<pair<bool, set<int> > > parts;
	vector<int> nodes(n + 8, -1);
	for (int i = 0; i < q; ++i) {
		if (i) {
			scanf("\n");
		}
		char type;
		scanf("%c", &type);
		if (type == '?') {
			int d;
			scanf("%d", &d);
			if (nodes[d] == -1) {
				printf("0");
			}
			else if (parts[nodes[d]].first) {
				printf("1");
			}
			else {
				printf("?");
			}
		}
		else if (type == '+') {
			int a, b;
			scanf("%d %d", &a, &b);
			if ((nodes[a] == -1) && (nodes[b] == -1)) {
				pair<bool, set<int> > part = make_pair(true, set<int>());
				part.second.insert(a);
				nodes[a] = parts.size();
				if (a != b) {
					part.second.insert(b);
					part.first = false;
					nodes[b] = parts.size();
				}
				parts.push_back(part);
			}
			else {
				int merge_from = a;
				int merge_into = b;
				if ((nodes[b] == -1) || ((nodes[a] != -1) && (parts[nodes[a]].second.size() > parts[nodes[b]].second.size()))) {
					merge_from = b;
					merge_into = a;
				}
				if (nodes[merge_from] != -1) {
					if (nodes[merge_from] == nodes[merge_into]) {
						parts[nodes[merge_from]].first = true;
					}
					else {
						if (parts[nodes[merge_from]].first) {
							parts[nodes[merge_into]].first = true;
						}
						int nmf = nodes[merge_from];
						int nmi = nodes[merge_into];
						for (set<int>::iterator it = parts[nmf].second.begin(); it != parts[nmf].second.end(); it++) {
							nodes[*it] = nmi;
							parts[nmi].second.insert(*it);
						}
					}
				}
				else {
					nodes[merge_from] = nodes[merge_into];
					parts[nodes[merge_into]].second.insert(merge_from);
				}
			}
		}
		else { // type == '-'
			int c;
			scanf("%d", &c);
			parts[nodes[c]].second.erase(c);
			if ((parts[nodes[c]].second.size() == 1) && !parts[nodes[c]].first) {
				nodes[*parts[nodes[c]].second.begin()] = -1;
			}
			nodes[c] = -1;
		}
	}
	printf("\n");
	return 0;
}