记录 up[x] 表示 x 上方有多少个
all[x] 表示当前连通的有多少个
find 的时候 和 合并的时候 更新一下即可
——代码
1 #include <cstdio> 2 #include <iostream> 3 #define N 30001 4 #define abs(x) ((x) < 0 ? -(x) : (x)) 5 6 int T; 7 int f[N], up[N], all[N]; 8 9 inline int read() 10 { 11 int x = 0, f = 1; 12 char ch = getchar(); 13 for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1; 14 for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0'; 15 return x * f; 16 } 17 18 inline int find(int x) 19 { 20 if(x ^ f[x]) 21 { 22 int fx = f[x]; 23 f[x] = find(f[x]); 24 up[x] += up[fx]; 25 } 26 return f[x]; 27 } 28 29 int main() 30 { 31 int i, x, y, fx, fy; 32 char s[1]; 33 T = read(); 34 for(i = 1; i < N; i++) f[i] = i, all[i] = 1; 35 while(T--) 36 { 37 scanf("%s", s); 38 x = read(); 39 y = read(); 40 fx = find(x); 41 fy = find(y); 42 if(s[0] == 'M') 43 { 44 f[fx] = fy; 45 up[fx] += all[fy]; 46 all[fy] += all[fx]; 47 } 48 else fx ^ fy ? puts("-1") : printf("%d ", abs(up[x] - up[y]) - 1); 49 } 50 return 0; 51 }