并查集+dfs+带根值合并与到点的距离处理
O(n)
#include<bits/stdc++.h>
using namespace std;
const int N = 3e4 + 5;
int d[N],p[N],s[N];
int n,t;
int find(int x) {
if(p[x] != x) {
int t = find(p[x]);
d[x] += d[p[x]];
return p[x] = t;
}
return p[x];
}
int main() {
cin>>t;
for(int i = 1; i<= N - 1; ++i) {
p[i] = i;
s[i] = 1;
}
while(t--) {
char c;
cin>>c;
int x,y;
cin>>x>>y;
if(c=='M' ) {
x = find(x),y = find(y);
if(x!=y) {
d[x] = s[y];
s[y] += s[x];
p[x] = y;
}
}
else {
int xx = find(x),yy = find(y);
if(xx!=yy) cout<<"-1\n";
else {
cout<<max(abs(d[x]-d[y])-1,0)<<"\n";
}
}
}
}