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
|
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
const int N = 3e4+10;
int p;
int fa[N];
int vis[N];
int dep[N], son[N];
int Find(int x) {
if(fa[x] == x) return x;
int y = fa[x];
fa[x] = Find(fa[x]);
dep[x] += dep[y];
return fa[x];
}
bool Union(int x, int y) {
x = Find(x);
y = Find(y);
if(x != y) {
fa[y] = x;
dep[y] = son[x];
son[x] += son[y];
return true;
}
return false;
}
int main() {
cin >> p;
for(int i = 1; i <= N; i++) fa[i] = i, son[i] = 1;
while (p--) {
char ch;
cin >> ch;
if(ch == 'M') {
int a, b;
scanf("%d%d", &a, &b);
Union(a, b);
} else if( ch == 'C') {
int a;
scanf("%d", &a);
printf("%d\n", son[Find(a)] - dep[a] - 1);
}
}
return 0;
}
|
